来源Leetcode第129题求根到叶子节点数字之和
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
1
2
3
4
5
6
7
8
9
| 输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
|
DFS
跟之前写的路径总和差不多，也是要注意DFS在返回时需要去掉最后一个加入的点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int ans = 0;
public int sumNumbers(TreeNode root) {
if(root == null)
return ans;
helper(root,ans);
return ans;
}
public void helper(TreeNode root,int sum){
if(root != null)
sum = sum * 10 + root.val;
else
return;
if(root.left == null && root.right == null)
ans += sum;
if(root.left != null)
helper(root.left,sum);
if(root.right != null)
helper(root.right,sum);
sum /= 10;
return;
}
|
栈
来源题解
通常还可以用 stack 的思路来解递归的题目。先序非递归的代码我们知道是用 stack 来保存遍历过的元素。而因为本题要记录到叶节点的数字，所以需要一个额外的 stack 来记录数字。每次出 stack 之后，如果是叶子节点，那么加和；如果不是，那么就看左右子树，入 stack。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public int sumNumbers(TreeNode root) {
int sum = 0;
if (root == null) return sum;
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Integer> numStack = new Stack<>();
nodeStack.add(root);
numStack.add(0);
while (!nodeStack.isEmpty()) {
TreeNode current = nodeStack.pop();
Integer currentNum = numStack.pop() * 10 + current.val;
if (current.left == null && current.right == null) {
sum += currentNum;
}
if (current.left != null) {
nodeStack.add(current.left);
numStack.add(currentNum);
}
if (current.right != null) {
nodeStack.add(current.right);
numStack.add(currentNum);
}
}
return sum;
}
|