453，DFS和BFS解求根到叶子节点数字之和

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

If you wish to survive you need to cultivate a strong mental attitude.

如果你想活着，需要培养一颗坚强的心。

问题描述

给定一个二叉树，它的每个结点都存放一个 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.

DFS解决

这题说的是每条从根节点到叶子结点的路径都代表一个数字，然后再把这些数字加起来即可。遍历一棵树从根节点到叶子结点的所有路径，最容易想到的是DFS，所以这题使用DFS是最容易解决的。如果对二叉树的DFS不熟悉的话，可以看下373，数据结构-6,树

解决方式就是从根节点往下走的时候，那么当前节点的值就是父节点的值*10+当前节点的值。默认根节点的父节点的值是0，如果到达叶子结点，就用一个全局的变量把叶子结点的值加起来。这里就以示例2为例来画个图看一下

搞懂了上的分析过程，代码就容易多了

 1public int sumNumbers(TreeNode root) {
 2    //如果根节点是空，直接返回0即可
 3    if (root == null)
 4        return 0;
 5    //两个栈，一个存储的是节点，一个存储的是节点对应的值
 6    Stack<TreeNode> nodeStack = new Stack<>();
 7    Stack<Integer> valueStack = new Stack<>();
 8    //全局的，统计所有路径的和
 9    int res = 0;
10    nodeStack.add(root);
11    valueStack.add(root.val);
12    while (!nodeStack.isEmpty()) {
13        //当前节点和当前节点的值同时出栈
14        TreeNode node = nodeStack.pop();
15        int value = valueStack.pop();
16        if (node.left == null && node.right == null) {
17            //如果当前节点是叶子结点，说明找到了一条路径，把这条
18            //路径的值加入到全局变量res中
19            res += value;
20        } else {
21            //如果不是叶子节点就执行下面的操作
22            if (node.right != null) {
23                //把子节点和子节点的值分别加入到栈中，这里子节点的值
24                //就是父节点的值*10+当前节点的值
25                nodeStack.push(node.right);
26                valueStack.push(value * 10 + node.right.val);
27            }
28            if (node.left != null) {
29                nodeStack.push(node.left);
30                valueStack.push(value * 10 + node.left.val);
31            }
32        }
33    }
34    return res;
35}

如果嫌上面代码多，也可以改为递归的方式

 1public int sumNumbers(TreeNode root) {
 2    return dfs(root, 0);
 3}
 4
 5private int dfs(TreeNode root, int sum) {
 6    //终止条件的判断
 7    if (root == null)
 8        return 0;
 9    //计算当前节点的值
10    sum = sum * 10 + root.val;
11    //如果当前节点是叶子节点，说明找到了一条完整路径，直接
12    //返回这条路径的值即可
13    if (root.left == null && root.right == null)
14        return sum;
15    //如果当前节点不是叶子结点，返回左右子节点的路径和
16    return dfs(root.left, sum) + dfs(root.right, sum);
17}

BFS解决

对于树的遍历，我们知道除了前序中序后续遍历以外，还有DFS和BFS，DFS上面已经讲过了，下面再来看一下BFS，他是一层一层的遍历的，就像下面这样，如果不太懂的也可以先看下373，数据结构-6,树

原理和上面DFS类似，每遍历一个结点，我们就要重新计算当前节点的值，那么当前节点的值就是父节点的值*10+当前节点的值。

 1public int sumNumbers(TreeNode root) {
 2    //边界条件的判断
 3    if (root == null)
 4        return 0;
 5    Queue<TreeNode> nodeQueue = new LinkedList<>();
 6    Queue<Integer> valueQueue = new LinkedList<>();
 7    int res = 0;
 8    nodeQueue.add(root);
 9    valueQueue.add(root.val);
10    while (!nodeQueue.isEmpty()) {
11        //节点和节点对应的值同时出队
12        TreeNode node = nodeQueue.poll();
13        int value = valueQueue.poll();
14        if (node.left == null && node.right == null) {
15            //如果当前节点是叶子结点，说明找到了一条路径，把这条
16            //路径的值加入到全局变量res中
17            res += value;
18        } else {
19            //如果不是叶子节点就执行下面的操作
20            if (node.left != null) {
21                //把子节点和子节点的值分别加入到队列中，这里子节点的值
22                //就是父节点的值*10+当前节点的值
23                nodeQueue.add(node.left);
24                valueQueue.add(value * 10 + node.left.val);
25            }
26            if (node.right != null) {
27                nodeQueue.add(node.right);
28                valueQueue.add(value * 10 + node.right.val);
29            }
30        }
31    }
32    return res;
33}