题解 | #二叉树根节点到叶子节点的所有路径和#

dfs遍历每一个节点，时间复杂度O（n），因为每个节点只遍历一次，空间复杂度取决于递归的深度，最坏为O（n）。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
        // write code here
        if (root == null) return 0;
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int preSum) {
        if (root == null) return 0;
        int sum = preSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        } else {
            return dfs(root.left, sum) + dfs(root.right, sum);
        }
    }
}