LeetCode 129. 求根节点到叶节点数字之和
题目描述
思路分析
dfs
bfs
参考代码
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
30
31
32
33
34
35
36
37
38
39
40
41
func sumNumbers(root *TreeNode) int {
if root == nil {
return 0
}
sum := 0
queue := []struct {
node *TreeNode
val int
}
for len(queue) > 0 {
// 取出队列的第一个元素
cur := queue[0]
queue = queue[1:]
node := cur.node
val := cur.val
// 如果是叶节点，累加到总和
if node.Left == nil && node.Right == nil {
sum += val
}
if node.Left != nil {
queue = append(queue, struct {
node *TreeNode
val int
}{node.Left, val*10 + node.Left.Val})
}
if node.Right != nil {
queue = append(queue, struct {
node *TreeNode
val int
}{node.Right, val*10 + node.Right.Val})
}
}
return sum
}
- 时间复杂度：
O(n)，其中n是树中节点的数量，因为每个节点都需要被访问一次。- 空间复杂度：
O(w)，其中w是树的最大宽度，队列的空间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func sumNumbers(root *TreeNode) int {
return sumHelper(root, 0)
}
func sumHelper(node *TreeNode, currentSum int) int {
if node == nil {
return 0
}
// 更新当前路径的数字
currentSum = currentSum*10 + node.Val
// 如果是叶节点，返回当前路径的数字
if node.Left == nil && node.Right == nil {
return currentSum
}
// 递归计算左子树和右子树的和
return sumHelper(node.Left, currentSum) + sumHelper(node.Right, currentSum)
}
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！