【LeetCode】129.求根节点到叶节点数字之和

1 问题

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的所有数字之和。

叶节点 是指没有子节点的节点。

示例 1

示例1

输入：root = [1,2,3]
输出：25
解释：

• 从根到叶子节点路径 1->2 代表数字 12
• 从根到叶子节点路径 1->3 代表数字 13
• 因此，数字总和 = 12 + 13 = 25

示例 2

示例2

输入：root = [4,9,0,5,1]
输出：1026
解释：

• 从根到叶子节点路径 4->9->5 代表数字 495
• 从根到叶子节点路径 4->9->1 代表数字 491
• 从根到叶子节点路径 4->0 代表数字 40
• 因此，数字总和 = 495 + 491 + 40 = 1026

提示

• 树中节点的数目在范围 [1, 1000] 内
• 0 <= Node.val <= 9
• 树的深度不超过 10

2 解题思路

2.1 DFS

• 对于叶子节点，将父节点的临时节点之和*10，再加上当前节点值，即可得到根节点到该节点的数值；并将其与目前已知的和sum相加，得到新的sum；
• 对于左节点不为空的，将当前的临时节点之和*10，再加上当前节点值，递归带入；
• 同理，对于右节点一样。

2.2 回溯法

也属于递归，常用的地方，比如字符串的全排列或组合。
具体原理和公式，可参见【LeetCode】46.全排列.

3 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum = 0;

    /** DFS */
    public int sumNumbers2(TreeNode root) {
        addChildren(root, 0);
        return sum;
    }

    private void addChildren(TreeNode child, int tempSum) {
        if (null == child) {
            return;
        }
        //add the current node's value
        tempSum *= 10;
        tempSum += child.val;
        //child is a leaf node
        if (null == child.left && null == child.right) {
            sum += tempSum;
            return;
        }
        if (null != child.left) {
            addChildren(child.left, tempSum);
        }
        if (null != child.right) {
            addChildren(child.right, tempSum);
        }
    }

    /** backtrack */
    public int sumNumbers(TreeNode root) {
        LinkedList<Integer> track = new LinkedList();
        track.add(root.val);
        backtrack(root, track);
        return sum;
    }

    private void backtrack(TreeNode root, LinkedList<Integer> track) {
        if (null == root) {
            return;
        }
        if (null == root.left && null == root.right) {
            sum += listToInt(new LinkedList(track));
            return;
        }
        if (null != root.left) {
            track.add(root.left.val);
            backtrack(root.left, track);
            track.removeLast();
        }
        if (null != root.right) {
            track.add(root.right.val);
            backtrack(root.right, track);
            track.removeLast();
        }
    }

    private int listToInt(LinkedList<Integer> list) {
        int sum = 0;
        for (Integer i : list) {
            sum = sum * 10 + i;
        }
        return sum;
    }
}