Links

34.二叉树中和为某一值的路径

题目

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例: 给定如下二叉树,以及目标和 target = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
提示:
节点总数 <= 10000

题解

将问题拆解为子树的问题,递归解决
func pathSum(_ root: TreeNode?, _ target: Int) -> [[Int]] {
guard let rootV = root?.val else {
return []
}
var result: [[Int]] = []
let deta = target - rootV
var temp: [TreeNode] = []
if let left = root?.left {
temp.append(left)
}
if let right = root?.right {
temp.append(right)
}
if temp.isEmpty { // 到达叶节点了
if target == rootV {
result.append([rootV])
}
}
else {
temp.forEach { tree in
pathSum(tree, deta).forEach { datas in
result.append([rootV] + datas)
}
}
}
return result
}
01