1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
private int ans;
public int sumNumbers(TreeNode root) {
dfs(root, 0);
return ans;
}
private void dfs(TreeNode node, int numAbove) {
if (node == null) {
return;
}
int currNum = numAbove * 10 + node.val;
if (node.left == null && node.right == null) {
ans += currNum;
return;
}
dfs(node.left, currNum);
dfs(node.right, currNum);
}
}
|
等于是每一个node可以得到从root到它这里组成的数字是多少. 然后我们把这个数字乘10在加上当前node得val就是从root到这个node组成的数字了. 只有当node是leaf node的时候, 我们才往ans上加东西.
时间复杂度: O(n)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
private int ans;
public int sumNumbers(TreeNode root) {
int ans = 0;
Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
stack.push(new Pair(root, 0));
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> currPair = stack.pop();
TreeNode currNode = currPair.getKey();
int currNum = currPair.getValue();
if (currNode != null) {
currNum = currNum * 10 + currNode.val;
if (currNode.left == null && currNode.right == null) {
ans += currNum;
} else {
stack.push(new Pair(currNode.left, currNum));
stack.push(new Pair(currNode.right, currNum));
}
}
}
return ans;
}
}
|
Iterative 版本的pre-order traversal.
