题解 | JAVA DFS#二叉树根节点到叶子节点的所有路径和# [P0-T2]

DFS
DFS时传递parentSum, childSum = parentSum*10 + child.val
时间O(n): 每个node访问一次
空间O(n): 因为是recursion，worst-case树是长条 所有node都在栈上

public class Solution {
    public int sumNumbers (TreeNode root) {
      return rec(root, 0);
    }
  
    public int rec(TreeNode root, int parentSum) {
      if (root == null) 
        return 0;
      
      int curSum = parentSum * 10 + root.val;
      if (root.left == null && root.right == null)
        return curSum;
      
      return rec(root.left, curSum) + rec(root.right, curSum);
    }
}