Implementation
int sumNumbers(Node root) {
return dfs(root, 0);
}
int dfs(Node n, int cur) {
if (n == null) return 0;
cur = cur * 10 + n.val;
if (n.left == null && n.right == null) return cur;
return dfs(n.left, cur) + dfs(n.right, cur);
}Advertisement
The trick
Pass accumulated number down. At leaf, return it. Otherwise recurse and sum.
Advertisement
Complexity
O(N) time, O(H) space.
Iterative variant
Stack of (node, cumulative) pairs. Same logic.