LeetCode 112. 路径总和
题目描述
思路分析
- 使用队列进行迭代：我们可以使用队列来实现广度优先搜索，逐层遍历树的节点。
- 存储节点和当前目标和：在队列中存储每个节点及其对应的目标和，逐层向下遍历。
- 判断叶子节点：当到达叶子节点时，检查当前的目标和是否为 0。如果是，则说明找到了符合条件的路径。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func hasPathSum(root *TreeNode, targetSum int) bool {
// 如果根节点为空，返回 false
if root == nil {
return false
}
// 如果是叶子节点，检查路径和
if root.Left == nil && root.Right == nil {
return root.Val == targetSum
}
// 递归检查左右子树，更新目标和
targetSum -= root.Val
return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum)
}
- 时间复杂度：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
37
type NodeInfo struct {
node *TreeNode
cur int
}
func hasPathSum(root *TreeNode, targetSum int) bool {
if root == nil {
return false
}
queue := []NodeInfo
for len(queue) > 0 {
front := queue[0]
queue = queue[1:]
curNode := front.node
curSum := front.cur
// 判断是否为叶子节点
if curNode.Left == nil && curNode.Right == nil {
if curSum == targetSum {
return true
}
}
if curNode.Left != nil {
queue = append(queue, NodeInfo{node: curNode.Left, cur: curSum + curNode.Left.Val})
}
if curNode.Right != nil {
queue = append(queue, NodeInfo{node: curNode.Right, cur: curSum + curNode.Right.Val})
}
}
return false
}
- 时间复杂度：O (N)，其中 N 是二叉树的节点数。我们需要遍历每个节点一次。
- 空间复杂度：O (W)，其中 W 是二叉树的最大宽度。在最坏情况下，队列的空间复杂度为 O (W)。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！