LeetCode 112. 路径总和
题目描述
思路分析
二叉树路径总和问题
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func hasPathSum(root *TreeNode, targetSum int) bool {
// 空树直接返回 false
if root == nil {
return false
}
// 如果是叶子节点，判断是否满足条件
if root.Left == nil && root.Right == nil {
return targetSum == root.Val
}
// 递归判断左右子树是否存在满足的路径
left := hasPathSum(root.Left, targetSum-root.Val)
right := hasPathSum(root.Right, targetSum-root.Val)
return left || right
}
- 时间复杂度：O(n)，n 是节点总数。
- 空间复杂度：O(h)，h 是树的高度。
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
func hasPathSum(root *TreeNode, targetSum int) bool {
if root == nil {
return false
}
type pair struct {
node *TreeNode
sum int
}
queue := []pair{
{root, root.Val},
}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
node := cur.node
sum := cur.sum
// 如果是叶子节点，判断路径和是否等于目标
if node.Left == nil && node.Right == nil && sum == targetSum {
return true
}
if node.Left != nil {
queue = append(queue, pair{node.Left, sum + node.Left.Val})
}
if node.Right != nil {
queue = append(queue, pair{node.Right, sum + node.Right.Val})
}
}
return false
}
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！