1，DFS解决
这题说的是每条从根节点到叶子结点的路径都代表一个数字，然后再把这些数字加起来即可。遍历一棵树从根节点到叶子结点的所有路径，最容易想到的是DFS，所以这题使用DFS是最容易解决的。如果对二叉树的DFS不熟悉的话，可以看下373，数据结构-6,树
解决方式就是从根节点往下走的时候，那么当前节点的值就是父节点的值*10+当前节点的值。默认根节点的父节点的值是0，如果到达叶子结点，就用一个全局的变量把叶子结点的值加起来。这里就以示例2为例来画个图看一下
搞懂了上的分析过程，代码就容易多了
public int sumNumbers(TreeNode root) {
//如果根节点是空，直接返回0即可
if (root == null)
return 0;
//两个栈，一个存储的是节点，一个存储的是节点对应的值
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Integer> valueStack = new Stack<>();
//全局的，统计所有路径的和
int res = 0;
nodeStack.add(root);
valueStack.add(root.val);
while (!nodeStack.isEmpty()) {
//当前节点和当前节点的值同时出栈
TreeNode node = nodeStack.pop();
int value = valueStack.pop();
if (node.left == null && node.right == null) {
//如果当前节点是叶子结点，说明找到了一条路径，把这条
//路径的值加入到全局变量res中
res += value;
} else {
//如果不是叶子节点就执行下面的操作
if (node.right != null) {
//把子节点和子节点的值分别加入到栈中，这里子节点的值
//就是父节点的值*10+当前节点的值
nodeStack.push(node.right);
valueStack.push(value * 10 + node.right.val);
}
if (node.left != null) {
nodeStack.push(node.left);
valueStack.push(value * 10 + node.left.val);
}
}
}
return res;
} 时间复杂度：O(n)，n是二叉树的节点个数。
空间复杂度：O(n)，使用两个栈
看一下运行结果
2，BFS解决
对于树的遍历，我们知道除了前序中序后续遍历以外，还有DFS和BFS，DFS上面已经讲过了，下面再来看一下BFS，他是一层一层的遍历的，就像下面这样，如果不太懂的也可以先看下373，数据结构-6,树
原理和上面DFS类似，每遍历一个结点，我们就要重新计算当前节点的值，那么当前节点的值就是父节点的值*10+当前节点的值。
public int sumNumbers(TreeNode root) {
//边界条件的判断
if (root == null)
return 0;
Queue<TreeNode> nodeQueue = new LinkedList<>();
Queue<Integer> valueQueue = new LinkedList<>();
int res = 0;
nodeQueue.add(root);
valueQueue.add(root.val);
while (!nodeQueue.isEmpty()) {
//节点和节点对应的值同时出队
TreeNode node = nodeQueue.poll();
int value = valueQueue.poll();
if (node.left == null && node.right == null) {
//如果当前节点是叶子结点，说明找到了一条路径，把这条
//路径的值加入到全局变量res中
res += value;
} else {
//如果不是叶子节点就执行下面的操作
if (node.left != null) {
//把子节点和子节点的值分别加入到队列中，这里子节点的值
//就是父节点的值*10+当前节点的值
nodeQueue.add(node.left);
valueQueue.add(value * 10 + node.left.val);
}
if (node.right != null) {
nodeQueue.add(node.right);
valueQueue.add(value * 10 + node.right.val);
}
}
}
return res;
} 时间复杂度：O(n)，n是二叉树的节点个数，所有节点都要访问一遍
空间复杂度：O(n)，使用两个队列
看一下运行结果
截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
京公网安备 11010502036488号