题目描述

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

示例 2:

输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

解法1 – 先序遍历

按照题目的描述，很自然就能够想到使用先序遍历访问二叉树，我们使用变量accu累积从跟节点到当前节点走过的节点构成到数字，其中accu = accu*10 + node.val。当我们走到叶节点时，将accu累加到结果ans[0]中。由于Java不支持引用传参(pass-by-reference)，我们使用1个元素的数组来存放结果，当然也可以通过成员变量来实现。

时间复杂度O(n)，空间复杂度O(n)（调用栈开销）。全部代码如下：

class Solution {
    public int sumNumbers(TreeNode root) {
        int[] ans = new int[1];

        helper(root, 0, ans);

        return ans[0];
    }

    private void helper(TreeNode node, int accu, int[] ans) {

        if (node == null)
            return;

        accu = accu * 10 + node.val;

        if (node.left == null && node.right == null)
            ans[0] += accu;
        else {
            helper(node.left, accu, ans);
            helper(node.right, accu, ans);
        }

    }
}

解法2 – 层次遍历

这道题也可以采用BFS方法来做。我们设置两个队列，一个是nodeQueue，用于记录当前节点下一层待访问的节点；另一个是accuQueue，用于记录从跟节点到当前节点路径构成的数字，这两个队列是保持同步的。

我们首先将跟节点入队nodeQueue，跟节点的值入队accuQueue，还设置一个ans变量用存放结果。当队列不为空时，我们从nodeQueue取出节点node，从accuQueue取出路径构成的数字accu，如果node是叶子节点，我们就把accu累加到ans；如果node的左子树非空，我们就将node.left入队nodeQueue，将accu*10 + node.left.val入队accuQueue；如果node右子树非空，就将node.right入队nodeQueue，将accu*10+node.right.val入队accuQueue。这样的操作不断地循环下去，直到队列为空，此时ans就已经累积了从跟节点到所有叶节点的数字和。

时间复杂度O(n)，空间复杂度O(n)，关于空间复杂度的分析参考这个。全部代码如下：

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int sumNumbers(TreeNode root) {
        int ans = 0;
        if (root == null)
            return ans;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> accuQueue = new LinkedList<>();

        nodeQueue.offer(root);
        accuQueue.offer(root.val);

        while (!nodeQueue.isEmpty()) {
            int size = nodeQueue.size();

            while (size-- > 0) {
                TreeNode node = nodeQueue.poll();
                int accu = accuQueue.poll();

                if (node.left == null && node.right == null)
                    ans += accu;
                else {
                    if (node.left != null) {
                        nodeQueue.offer(node.left);
                        accuQueue.offer(accu * 10 + node.left.val);
                    }
                    if (node.right != null) {
                        nodeQueue.offer(node.right);
                        accuQueue.offer(accu * 10 + node.right.val);
                    }
                }
            }
        }

        return ans;
    }
}