Practice
max_sum after the function completes?
Tree structure:
```
1
/
2 3
```
class TreeNode:
def __init__(self, val=0, left=null, right=null):
self.val = val
self.left = left
self.right = right
def maxPathSum(root):
if not root:
return 0
max_sum = float('-inf')
stack = []
node = root
last_visited = null
gain_map = {}
while stack or node:
if node:
stack.append(node)
node = node.left
else:
peek = stack[-1]
if peek.right and last_visited != peek.right:
node = peek.right
else:
left_gain = max(gain_map.get(peek.left, 0), 0)
right_gain = max(gain_map.get(peek.right, 0), 0)
current_path_sum = peek.val + left_gain + right_gain
max_sum = max(max_sum, current_path_sum)
gain_map[peek] = peek.val + max(left_gain, right_gain)
last_visited = stack.pop()
return max_sum
Solution
Step 1: Trace left subtree gain
Node 2 has no children, so left_gain=0, right_gain=0, current_path_sum=2, max_sum updated to 2, gain_map[2]=2.Step 2: Trace root and right subtree
Node 3 has no children, current_path_sum=3, max_sum updated to 3, gain_map[3]=3. For root 1, left_gain=2, right_gain=3, current_path_sum=1+2+3=6, max_sum updated to 6.Final Answer:
Option C -> Option CQuick Check:
Sum of path 2 -> 1 -> 3 is 6 [OK]
- Ignoring one child's gain leads to 5 or 4
- Off-by-one in gain_map updates
- Returning partial sums instead of max path sum
Solution
Step 1: Understand traversal constraints
Without left/right child pointers, Morris traversal is not applicable since it relies on child links.Step 2: Use parent pointers to simulate traversal
By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.Final Answer:
Option D -> Option DQuick Check:
Tracking previous node enables correct traversal without extra space [OK]
- Trying to create threads on parent pointers
- Using recursion without child pointers
- Confusing BFS with inorder traversal
Solution
Step 1: Recognize diameter depends on path length (edges), not node values.
Negative values do not affect height or path length calculations.Step 2: Confirm standard height-based diameter algorithm works unchanged.
Heights and diameter calculations rely on structure, so no changes are needed.Final Answer:
Option A -> Option AQuick Check:
Diameter depends on edges, not node values [OK]
- Confusing diameter with max sum path
- Ignoring negative nodes incorrectly
- Switching to BFS unnecessarily
Solution
Step 1: Understand the reuse constraint
Allowing multiple robberies per node breaks the tree structure assumption and simple one-time visit DFS.Step 2: Identify necessary algorithmic change
We must track states including how many times a node is robbed and ensure adjacency constraints per robbery. Memoization keyed by node and robbing state prevents exponential recomputation.Step 3: Why other options fail
Use the same DFS with two-value return; no changes needed since adjacency constraints remain. ignores reuse; Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection. is overcomplicated and unnecessary since the structure is still a tree; Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse. is vague and does not address adjacency constraints properly.Final Answer:
Option D -> Option DQuick Check:
Memoization with extended state handles reuse and adjacency constraints [OK]
- Assuming original DFS suffices for reuse
- Ignoring adjacency constraints when reusing nodes
Solution
Step 1: Understand path direction relaxation
Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.Step 2: Model tree as undirected graph and run DFS from every node
To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.Final Answer:
Option A -> Option AQuick Check:
Undirected DFS from every node with prefix sums counts all connected paths [OK]
- Trying to reuse one-directional prefix sum DFS without modification
- Assuming running DFS twice covers all paths
- Trying to store both directions in one prefix sum map
