LeetCode: Binary Tree Cameras

## 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
}