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.