HardNo. 0968
Binary Tree Cameras — LeetCode 968 Python Solution
- Pattern
- Tree Traversal
- Topics
- Tree, Depth-First Search, Dynamic Programming, Binary Tree
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.
Example
- Input
- root = [0,0,null,0,0]
- Output
- 1
- Explanation
- One camera is enough to monitor all nodes if placed as shown.
Python solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minCameraCover(self, root: Optional[TreeNode]) -> int:
def dfs(root):
if root is None:
return inf, 0, 0
la, lb, lc = dfs(root.left)
ra, rb, rc = dfs(root.right)
a = min(la, lb, lc) + min(ra, rb, rc) + 1
b = min(la + rb, lb + ra, la + ra)
c = lb + rb
return a, b, c
a, b, _ = dfs(root)
return min(a, b)Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the number of nodes in the binary tree
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 968. Binary Tree Cameras is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0124 | Binary Tree Maximum Path Sum | Hard |
| 0337 | House Robber III | Medium |
| 1372 | Longest ZigZag Path in a Binary Tree | Medium |
| 1373 | Maximum Sum BST in Binary Tree | Hard |
| 0095 | Unique Binary Search Trees II | Medium |
| 0096 | Unique Binary Search Trees | Medium |
Frequently asked questions
- How hard is LeetCode 968. Binary Tree Cameras?
LeetCode 968. Binary Tree Cameras is rated Hard on LeetCode.
- What is the time complexity of LeetCode 968. Binary Tree Cameras?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 968. Binary Tree Cameras?
The Python solution on this page uses O(n), where n is the number of nodes in the binary tree auxiliary space.
- What topics does LeetCode 968. Binary Tree Cameras cover?
LeetCode 968. Binary Tree Cameras is tagged Tree, Depth-First Search, Dynamic Programming and Binary Tree on LeetCode.