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

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

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

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

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

示例 1：

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

示例 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

DFS，归并，有返回值有信息参数的DFS，

承上启下，检查叶子节点。当前路径和作为递归参数

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0); // 调用深度优先搜索从根节点开始计算路径和
    }

    public int dfs(TreeNode root, int prevNum) {
        // 特殊条件：如果当前节点为空，返回0。注意要返回0而不是prevNum，因为如果当前节点为空，说明不存在这条路径，自然对累积和没有贡献。
        if (root == null) {
            return 0;
        }

        // 从根节点到当前节点的路径和+当前节点的左右子树的路径和。
        int pathNum = prevNum * 10 + root.val; // 更新当前路径的累积和，它会做为参数被传递给下一层递归。
        if (root.left == null && root.right == null) { // 结束条件，如果当前节点是叶子节点
            return pathNum; // 返回当前路径表示的数字
        }
        // 如果当前节点不是叶子节点，递归计算左右子树的路径和并返回它们的和
        return dfs(root.left, pathNum) + dfs(root.right, pathNum);
    }
}

• 时间复杂度：O(n)，其中 n 是二叉树的节点个数。对每个节点访问一次。
• 空间复杂度：O(n)，其中 n 是二叉树的节点个数。空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下，二叉树的高度等于节点个数，空间复杂度为 O(n)。

回溯。无返回值无信息参数的DFS，全局变量。

每找到一条路径，就把路径对应的数字加到结果上去。

class Solution {
    StringBuilder path = new StringBuilder();
    int res = 0;

    public int sumNumbers(TreeNode root) {
        // 遍历一遍二叉树就能出结果
        traverse(root);
        return res;
    }

    // 二叉树遍历函数
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        
        // 前序遍历位置，记录节点值。递归有过去和将来，把当前值累加到历史值上，然后前进。
        path.append(root.val);
        // 结束条件：找到一条路径。
        if (root.left == null && root.right == null) {
            // 到达叶子节点，累加路径和。重点。注意这里不能直接return，因为还要回溯。
            res += Integer.parseInt(path.toString());
        }
        // 二叉树递归框架，遍历左右子树
        traverse(root.left);
        traverse(root.right);
        // 后续遍历位置，撤销节点值
        path.deleteCharAt(path.length() - 1);
    }
}

• 时间复杂度：O(n)，其中 n 是二叉树的节点个数。对每个节点访问一次。
• 空间复杂度：O(n)，其中 n 是二叉树的节点个数。空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下，二叉树的高度等于节点个数，空间复杂度为 O(n)。

BFS

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0; // 如果根节点为空，返回0
        }
        
        int sum = 0; // 初始化总和为0
        Queue<TreeNode> nodeQueue = new LinkedList<>(); // 节点队列，用于层次遍历
        // 数字队列，用于存储路径表示的数字。重点。
        Queue<Integer> numQueue = new LinkedList<>(); 

        // 将根节点及其值加入队列
        nodeQueue.offer(root);
        numQueue.offer(root.val);
        
        // 层次遍历二叉树
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll(); // 获取当前节点
            int num = numQueue.poll(); // 获取当前路径表示的数字
            TreeNode left = node.left, right = node.right; // 获取左子节点和右子节点
            
            // 如果当前节点是叶子节点，累加当前路径表示的数字到总和
            if (left == null && right == null) {
                sum += num;
            } else {
                // 如果左子节点不为空，将其加入节点队列并更新路径表示的数字
                if (left != null) {
                    nodeQueue.offer(left);
                    numQueue.offer(num * 10 + left.val);
                }
                // 如果右子节点不为空，将其加入节点队列并更新路径表示的数字
                if (right != null) {
                    nodeQueue.offer(right);
                    numQueue.offer(num * 10 + right.val);
                }
            }
        }
        return sum; // 返回总和
    }
}

• 时间复杂度：O(n)，其中 n 是二叉树的节点个数。对每个节点访问一次。
• 空间复杂度：O(n)，其中 n 是二叉树的节点个数。空间复杂度主要取决于队列，每个队列中的元素个数不会超过 n。