题目描述

给定一个仅包含数字0-9的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是 1→2→3,那么这条路径就用 123 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：
图片说明
这颗二叉树一共有两条路径，根节点到叶子节点的路径 1→2 用数字 12 代替，根节点到叶子节点的路径 1→3 用数字 13 代替
所以答案为 12+13=25
示例1
输入：{1,0}
返回值：10

题目分析

想要获得所有的路径和，首先使用 dfs深度遍历（先序） 来遍历整个树，当遍历到叶子结点时，可说明遍历完一条路径，统计这条路径的结点和，最后将每条路径的和相加即为结果。
图片说明

解题思路

方法1：使用字符串记录所有路径，最后相加
①定义全局变量sum，统计所有路径和
②使用StringBuilder记录路径上经过的结点，path.append(node.val);
②将字符串转化为路径值，Integer.parseInt(path.toString()) 加到sum中;

方法2：计算每个结点到叶子结点的路径和，最后获得根结点的值
①遍历整个树，当前结点的路径和 = 左子节点和 + 右子节点和；
②每个结点的路径和sum需要移位， sum = sum * 10 + root.val;
③最后返回的是所有路径和。

代码实现

方法1：使用字符串记录所有路径，最后相加

    // 静态变量记录所有路径和
    public static int sum = 0;
    public int sumNumbers (TreeNode root) {
        // write code here
        if(root == null) return 0;
        backtrack(root, new StringBuilder());
        return sum;
    }

    public void backtrack(TreeNode root, StringBuilder path){
        // 到空结点返回
        if(root == null) return ;
        // 使用stringBuilder记录路径上叶子结点的数值
        path.append(root.val);
        if(root.left == null && root.right == null){
            // 到叶子结点为一条路径，将字符串转为数值
            int num = Integer.parseInt(path.toString());
            // 加入总和
            sum += num;
        }
        // 先序遍历整个树
        backtrack(root.left, path);
        backtrack(root.right, path);
        // 回退当前结点，字符串减少一个数
        path.deleteCharAt(path.length()-1);
    }

时间复杂度：O(n)，n是树的结点数，需要遍历整个树，时间复杂度为O(n)；
空间复杂度：O(n)，递归深度最大为n，空间复杂度为O(n)；

方法2：计算每个结点到叶子结点的路径和，最后获得根结点的值

public int sumNumbers (TreeNode root) {
        // write code here
        if(root == null) return 0;
        return backtrack(root, 0);
    }

    public int backtrack(TreeNode root, int sum){
        if(root == null) return 0;
        // 加入当前结点的值
        sum = sum * 10 + root.val;
        if(root.left == null && root.right == null){
            // 到叶子结点返回计算的值
            return sum;
        }
        // 未到叶子结点，则往左右子节点继续计算和
        return backtrack(root.left, sum) + backtrack(root.right, sum);
    }

时间复杂度：O(n)，n是树的结点数，需要遍历整个树，时间复杂度为O(n)；
空间复杂度：O(n)，递归深度最大为n，空间复杂度为O(n)；