# 129.求根节点到叶子节点数字之和
TIP
标签:树、深度优先搜索、二叉树
# 算法思路
这道题目中,二叉树的每条从根节点到叶子节点的路径都代表一个数字。
其实,每个节点都对应一个数字,等于其父亲节点对应的数字乘以10再加上该节点的值 (这里假设根节点的父节点对应的数字是 0),只要计算出每个叶子节点对应的数字,然后计算所有叶子节点对应的数字之和,就可以得出结果。
可以通过深度优先搜索来解决这道题目。
深度优先搜索是很直观的做法,从根节点开始,遍历每个节点,如果遇到叶子节点,则将叶子节点对应的数字加到数字之和,如果当前节点不是叶子节点,则计算其子节点对应的数字,然后对子节点进行递归。
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var dfs = function(root,preSum) {
if (root === null) {
return 0
}
const sum = preSum * 10 + root.val
if (root.left === null && root.right === null) {
return sum
} else {
return dfs(root.left, sum) + dfs(root.right, sum)
}
};
var sumNumbers = function(root) {
return dfs(root, 0)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29