Tree DP

Table of Contents

• 337. House Robber III (Medium)
• 968. Binary Tree Cameras (Hard)
• 2313. Minimum Flips in Binary Tree to Get Result (Hard) 👑

337. House Robber III

• LeetCode | LeetCode CH (Medium)

• Tags: dynamic programming, tree, depth first search, binary tree

968. Binary Tree Cameras

• LeetCode | LeetCode CH (Hard)

• Tags: dynamic programming, tree, depth first search, binary tree

968. Binary Tree Cameras - Python Solution

from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


def minCameraCover(root: Optional[TreeNode]) -> int:
    res = 0

    def dfs(node, hasParent):
        if not node:
            return -1

        nonlocal res
        left, right = dfs(node.left, True), dfs(node.right, True)

        if left == -1 and right == -1:
            if hasParent:
                return 0
            res += 1
            return 2
        if left == 0 or right == 0:
            res += 1
            return 2
        if left == 2 or right == 2:
            return 1
        if hasParent:
            return 0
        res += 1
        return 2

    dfs(root, False)

    return res


root = build([0, 0, None, 0, 0])
print(root)
print(minCameraCover(root))  # 1

2313. Minimum Flips in Binary Tree to Get Result

• LeetCode | LeetCode CH (Hard)

• Tags: dynamic programming, tree, depth first search, binary tree

Comments