Formatted question description: https://leetcode.ca/all/968.html

968. Binary Tree Cameras (Hard)

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0.

Companies:
Facebook

Related Topics:
Dynamic Programming, Tree, Depth-first Search

Solution 1.

Assumption: we can alter the value of the tree node.

Use postorder traversal. Let val convey the state of the node:

0 means uncovered.
1 means covered
2 means having camera

If node is NULL, we regard it as 1.

If either of my left/right child is uncovered, I have to put a camera.
Otherwise, if either of my left/right child has camera, I’m covered and skip me.
Otherwise (both children are covered), if I’m root, I have to put a camera.
Otherwise, skip me.

// OJ: https://leetcode.com/problems/binary-tree-cameras/
// Time: O(N)
// Space: O(logN)
class Solution {
private:
    TreeNode *R;
    int postorder(TreeNode* root) {
        if (!root) return 0;
        int ans = postorder(root->left) + postorder(root->right);
        int left = root->left ? root->left->val : 1;
        int right = root->right ? root->right->val : 1;
        if (left == 0 || right == 0) {
            root->val = 2;
            return ans + 1;
        } else if (left == 2 || right == 2) {
            root->val = 1;
            return ans;
        } else return root == R ? ans + 1 : ans;
    }
public:
    int minCameraCover(TreeNode* root) {
        R = root;
        return postorder(root);
    }
};

Solution 2.

If we can’t have the assumption in Solution 1, we can use the return value to return my state to my parent.

// OJ: https://leetcode.com/problems/binary-tree-cameras/
// Time: O(N)
// Space: O(logN)
class Solution {
private:
    int ans = 0;
    int postorder(TreeNode *root) {
        if (!root) return 1;
        int left = postorder(root->left);
        int right = postorder(root->right);
        if (left == 0 || right == 0) {
            ++ans;
            return 2;
        } else return left == 2 || right == 2 ? 1 : 0;
    }
public:
    int minCameraCover(TreeNode* root) {
        return postorder(root) == 0 ? ans + 1 : ans;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        if (root == null)
            return 0;
        List<TreeNode> list = new ArrayList<TreeNode>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node);
            TreeNode left = node.left, right = node.right;
            if (left != null)
                queue.offer(left);
            if (right != null)
                queue.offer(right);
        }
        Map<TreeNode, int[]> map = new HashMap<TreeNode, int[]>();
        for (int i = list.size() - 1; i >= 0; i--) {
            TreeNode node = list.get(i);
            if (node.left == null && node.right == null)
                map.put(node, new int[]{0, Integer.MAX_VALUE / 10, 1});
            else if (node.left == null) {
                int[] rightArray = map.get(node.right);
                int[] array = new int[3];
                array[0] = rightArray[1];
                array[1] = rightArray[2];
                array[2] = 1 + Math.min(rightArray[0], Math.min(rightArray[1], rightArray[2]));
                map.put(node, array);
            } else if (node.right == null) {
                int[] leftArray = map.get(node.left);
                int[] array = new int[3];
                array[0] = leftArray[1];
                array[1] = leftArray[2];
                array[2] = 1 + Math.min(leftArray[0], Math.min(leftArray[1], leftArray[2]));
                map.put(node, array);
            } else {
                int[] leftArray = map.get(node.left);
                int[] rightArray = map.get(node.right);
                int minLeft = Math.min(leftArray[1], leftArray[2]);
                int minRight = Math.min(rightArray[1], rightArray[2]);
                int[] array = new int[3];
                array[0] = leftArray[1] + rightArray[1];
                array[1] = Math.min(leftArray[2] + minRight, rightArray[2] + minLeft);
                array[2] = 1 + Math.min(leftArray[0], minLeft) + Math.min(rightArray[0], minRight);
                map.put(node, array);
            }
        }
        int[] rootArray = map.get(root);
        return Math.min(rootArray[1], rootArray[2]);
    }
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int ans;

    public int minCameraCover(TreeNode root) {
        ans = 0;
        return (dfs(root) == 0) ? ans + 1 : ans;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 2;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        if (left == 0 || right == 0) {
            ++ans;
            return 1;
        }
        if (left == 1 || right == 1) {
            return 2;
        }
        return 0;
    }
}

// OJ: https://leetcode.com/problems/binary-tree-cameras/
// Time: O(N)
// Space: O(logN)
class Solution {
private:
    TreeNode *R;
    int postorder(TreeNode* root) {
        if (!root) return 0;
        int ans = postorder(root->left) + postorder(root->right);
        int left = root->left ? root->left->val : 1;
        int right = root->right ? root->right->val : 1;
        if (left == 0 || right == 0) {
            root->val = 2;
            return ans + 1;
        } else if (left == 2 || right == 2) {
            root->val = 1;
            return ans;
        } else return root == R ? ans + 1 : ans;
    }
public:
    int minCameraCover(TreeNode* root) {
        R = root;
        return postorder(root);
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        def dfs(root):
            nonlocal ans
            if root is None:
                return 2
            left, right = dfs(root.left), dfs(root.right)
            if left == 0 or right == 0:
                ans += 1
                return 1
            return 2 if left == 1 or right == 1 else 0

        ans = 0
        return (dfs(root) == 0) + ans

############

# 968. Binary Tree Cameras
# https://leetcode.com/problems/binary-tree-cameras/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        res = 0
        
        def go(node):
            nonlocal res
            
            if not node: return 2
            
            left, right = go(node.left), go(node.right)
            
            if left == 0 or right == 0:
                res += 1
                return 1
            
            return 2 if left == 1 or right == 1 else 0
        
        return (go(root) == 0) + res

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minCameraCover(root *TreeNode) int {
	ans := 0
	var dfs func(root *TreeNode) int
	dfs = func(root *TreeNode) int {
		if root == nil {
			return 2
		}
		left, right := dfs(root.Left), dfs(root.Right)
		if left == 0 || right == 0 {
			ans++
			return 1
		}
		if left == 1 || right == 1 {
			return 2
		}
		return 0
	}
	if dfs(root) == 0 {
		return ans + 1
	}
	return ans
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function minCameraCover(root: TreeNode | null): number {
    const dfs = (root: TreeNode | null): number[] => {
        if (!root) {
            return [1 << 29, 0, 0];
        }
        const [la, lb, lc] = dfs(root.left);
        const [ra, rb, rc] = dfs(root.right);
        const a = 1 + Math.min(la, lb, lc) + Math.min(ra, rb, rc);
        const b = Math.min(la + ra, la + rb, lb + ra);
        const c = lb + rb;
        return [a, b, c];
    };
    const [a, b, _] = dfs(root);
    return Math.min(a, b);
}

968 - Binary Tree Cameras

968. Binary Tree Cameras (Hard)

Solution 1.

Solution 2.

All Problems

All Solutions

Welcome to Subscribe On Youtube

968. Binary Tree Cameras (Hard)

Solution 1.

Solution 2.

All Problems

All Solutions