LeetCode-Solutions/Python/binary-tree-cameras.py at master · sirkalcode/LeetCode-Solutions · GitHub

32 lines (28 loc) · 892 Bytes

# Time: O(n)

# Space: O(h)

# Definition for a binary tree node.

class TreeNode(object):

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution(object):

def minCameraCover(self, root):

"""

:type root: TreeNode

:rtype: int

"""

UNCOVERED, COVERED, CAMERA = range(3)

def dfs(root, result):

left = dfs(root.left, result) if root.left else COVERED

right = dfs(root.right, result) if root.right else COVERED

if left == UNCOVERED or right == UNCOVERED:

result[0] += 1

return CAMERA

if left == CAMERA or right == CAMERA:

return COVERED

return UNCOVERED

result = [0]

if dfs(root, result) == UNCOVERED:

result[0] += 1

return result[0]

Expand file tree