题目描述
给你二叉树的根节点root和一个整数目标和targetSum，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
*示例1
1
2
| 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
|
1
2
| 输入：root = [1,2,3], targetSum = 5
输出：[]
|
1
2
| 输入：root = [1,2], targetSum = 0
输出：[]
|
提示：
- 树中节点总数在范围
[0, 5000] 内
-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
题解
解法一：DFS遍历
借助三个栈同步记录：达到的节点、到达当前节点时的路径之和、到达当前节点时的所有路径
遍历节点栈：
同时取出三个栈上的末尾元素，如果当前节点为叶子节点且当前节点的路径之和等于目标值，那么放入到结果数组中；
其他情况则入栈子节点、子节点对应的路径之和和该叶子节点对应的路径，然后进入下一轮遍历。
注意：左右子树路径需要分别入栈，两个子树要各copy一份原路径后拼接当前叶子节点。若使用原来的路径进行拼接则是把左右子树放到了一个路径里）
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
| func pathSum(_ root: TreeNode?, _ targetSum: Int) -> [[Int]] {
guard let root = root else {
return []
}
var res = [[Int]]()
var nodeStack = [root]
var valStack = [root.val]
var pathStack = [[root.val]]
while !nodeStack.isEmpty {
let node = nodeStack.popLast()!
let val = valStack.popLast()!
let path = pathStack.popLast()!
if node.left === nil && node.right === nil && val == targetSum {
res.append(path)
} else {
if let left = node.left {
var leftPath = path
nodeStack.append(left)
valStack.append(left.val + val)
leftPath.append(left.val)
pathStack.append(leftPath)
}
if let right = node.right {
var rightPath = path
nodeStack.append(right)
valStack.append(right.val + val)
rightPath.append(right.val)
pathStack.append(rightPath)
}
}
}
return res
}
|
解法二：DFS递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func pathSum(_ root: TreeNode?, _ targetSum: Int) -> [[Int]] {
var res = [[Int]]()
var path = [Int]()
func dfs(_ cur: TreeNode?, _ curSum: Int) {
guard let cur = cur else {
return
}
path.append(cur.val)
let sum = curSum - cur.val
if cur.left === nil && cur.right === nil && sum == 0 {
res.append(path)
}
dfs(cur.left, sum)
dfs(cur.right, sum)
path.removeLast()
}
dfs(root, targetSum)
return res
}
|