Binary Tree Cameras

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #greedy, #binarytree, #dynamicprogramming, #treedp

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.

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

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution

## https://code.dennyzhang.com/binary-tree-cameras ## Basic Ideas: greedy + dfs ## ## Try to put camera to the immediate parent of leaves ## Then any following decisions are determined ## ## post order ## - covered by child ## - covered by itself ## - not covered ## ## Complexity: Time O(n), Space O(h) # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None COVER_BY_CHILD = 0 COVER_BY_ITSELF = 1 NOT_COVERED = 2 class Solution: def minCameraCover(self, root: TreeNode) -> int: camera = 0 def dfs(root): nonlocal camera # For empty node: ## no need for help from others; And can't help others if not root: return COVER_BY_CHILD # leaf: need help if not root.left and not root.right: return NOT_COVERED l = dfs(root.left) r = dfs(root.right) # Have to help if l == NOT_COVERED or r == NOT_COVERED: # add a camera camera += 1 return COVER_BY_ITSELF elif l == COVER_BY_ITSELF or r == COVER_BY_ITSELF: # child can help return COVER_BY_CHILD else: # need help from parent return NOT_COVERED if dfs(root) == NOT_COVERED: camera += 1 return camera

- Solution:

// https://code.dennyzhang.com/binary-tree-cameras // Basic Ideas: greedy // // Instead of placing camera in leaf nodes, better in the parent nodes // // Complexity: Time O(n) Space O(h) /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ // 0: need cover; 1: covered with camera; 2: covered without camera func dfs(root *TreeNode, res * int) int { // empty nodes: need cover. And can't help others if root == nil { return 2 } l, r := dfs(root.Left, res), dfs(root.Right, res) // parent of a leaf node if l == 0 || r == 0 { *res = *res + 1 return 1 } // Note: childrens are all covered if l == 1 || r == 1 { // children can cover parent return 2 } else { return 0 } } func minCameraCover(root *TreeNode) int { res := 0 if dfs(root, &res) == 0 { res++ } return res }