Binary Tree Cameras LeetCode solution in Python

1
import itertools
2

3

4
# Definition for a binary tree node.
5
# class TreeNode:
6
#     def __init__(self, val=0, left=None, right=None):
7
#         self.val = val
8
#         self.left = left
9
#         self.right = right
10
class Solution:
11
    def minCameraHelper(self, root: Optional[TreeNode]) -> (int, int):
12
        # Return 3 things:
13
        # cam, uncam, uncov
14
        # cam(era) is best score for valid tree with camera at root
15
        # uncam(era) is best score for valid tree without camera at root
16
        # uncov(ered) is best score for invalid tree, where the only invalidity (i.e. the only uncovered node) is the root node
17

18
        # Note: maxint (float("inf")) is used to signify situations that don't make sense or can't happen.
19
        # Anywhere there is a float("inf"), you can safely replace that with a 1 as 1 is as bad or worse than worst practical,
20
        # but I stick with maxint to highlight the nonsensical cases for the reader!
21

22
        if not root.left and not root.right:
23
            # base case: leaf
24
            # Note: "Uncam" setting doesn't make much sense (a leaf with no parents can either have a camera or be uncovered,
25
            #       but not covered with no camera)
26
            return 1, float("inf"), 0
27

28
        if root.left:
29
            left_cam, left_uncam, left_uncov = self.minCameraHelper(root.left)
30
        else:
31
            # base case: empty child
32
            # Need to prevent null nodes from providing coverage to parent, so set that cost to inf
33
            left_cam, left_uncam, left_uncov = float("inf"), 0, 0
34

35
        if root.right:
36
            right_cam, right_uncam, right_uncov = self.minCameraHelper(root.right)
37
        else:
38
            # base case: empty child
39
            # Need to prevent null nodes from providing coverage to parent, so set that cost to inf
40
            right_cam, right_uncam, right_uncov = float("inf"), 0, 0
41

42
        # Get the possible combinations for each setting
43
        cam_poss = itertools.product(
44
            [left_cam, left_uncam, left_uncov], [right_cam, right_uncam, right_uncov]
45
        )
46
        uncam_poss = [
47
            (left_cam, right_cam),
48
            (left_uncam, right_cam),
49
            (left_cam, right_uncam),
50
        ]
51
        uncov_poss = [(left_uncam, right_uncam)]
52

53
        # Compute costs for each setting
54
        cam = min([x + y for x, y in cam_poss]) + 1
55
        uncam = min([x + y for x, y in uncam_poss])
56
        uncov = min([x + y for x, y in uncov_poss])
57

58
        return cam, uncam, uncov
59

60
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
61
        cam, uncam, _ = self.minCameraHelper(root)
62
        return min(cam, uncam)