题目描述
输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
样例
给出二叉树如下所示,并给出num=22。
5
/ \
4 6
/ / \
12 13 6
/ \ / \
9 1 5 1
输出:[[5,4,12,1],[5,6,6,5]]
Go 代码
func findPath(root *TreeNode, sum int) [][]int {
var paths [][]int
if root == nil {
return paths
}
var path []int
path = append(path, root.Val)
// 如果为叶节点,并且路径和等于 sum,则将该路径(节点)加入路径集合
if root.Left == nil && root.Right == nil && sum - root.Val == 0 {
paths = append(paths, path)
}
// 从左路径集合中取路径,加上当前节点
if root.Left != nil {
leftPaths := findPath(root.Left, sum - root.Val)
for _, leftPath := range leftPaths {
tempPath := append(path, leftPath...)
paths = append(paths, tempPath)
}
}
// 从右路径集合中取路径,加上当前节点
if root.Right != nil {
rightPaths := findPath(root.Right, sum - root.Val)
for _, rightPath := range rightPaths {
tempPath := append(path, rightPath...)
paths = append(paths, tempPath)
}
}
return paths
}