Binary Tree Cameras - Solution & Explanation

The greedy DFS solution is based on a bottom-up approach. We classify each node into one of three states: covered by a camera, has a camera, or needs a camera. A node needs a camera if its children are not covered. We use a post-order DFS strategy to ensure all children are addressed before deciding the current node's state. The optimal way to cover a subtree is to place a camera on nodes whose children are not covered.

The code uses a post-order DFS traversal. It installs a camera at a node if either of its children need a camera (state 0). At the end, if the root itself needs a camera, we increment the count by one. Each node returns a state: 0 if it needs coverage, 1 if it has a camera, and 2 if it's covered.

This approach leverages dynamic programming through a recursive function with memoization to reduce redundant calculations. Each node can have three states represented in a tuple: it has a camera, it's covered but doesn't have a camera, or it's not covered. Using this state information, the solution calculates camera placements strategically.

This solution uses dynamic programming with memoization to avoid redundant recursive calls. The function `dfs` returns a tuple of three states for each node: the cost of having a camera, being covered without a camera, and not being covered.
The first element, `dp0`, calculates cost when a camera is placed at the current node. The second, `dp1`, calculates when the node is covered without having a camera, and the third, `dp2`, calculates when the node itself isn't covered.