Tree Dynamic Programming
Post-order DFS: compute answers bottom-up from leaves to root.
LC 337 (House Robber III), LC 124 (Binary Tree Max Path Sum), LC 543 (Diameter).
Key Insight: In tree DP we don't have a 1D/2D table.
Instead each node stores a small tuple of DP states.
House Robber III — for each node keep two values:
Processing order is post-order: children are fully solved before the parent.
House Robber III — for each node keep two values:
rob = max if we rob this node (cannot rob its children)skip = max if we skip this node (children may or may not be robbed)rob(v) = v.val + skip(L) + skip(R)skip(v) = max(rob(L),skip(L)) + max(rob(R),skip(R))Processing order is post-order: children are fully solved before the parent.
Not visited
Active (DFS)
Solved
Chosen (robbed)
Controls
Time: O(n) | Space: O(h)
Steps
0 stepsPress Run to trace the algorithm one step at a time.