AcWing 47. 二叉树中和为某一值的路径-Go代码
原题链接
中等
作者:
陈趫
,
2020-03-13 18:01:04
,
所有人可见
,
阅读 655
// 二叉树中节点之后等于某值的路径
func findPath(root *TreeNode, sum int) [][]int {
return dfsFindPath(root, sum, 0, [][]int{}, &list.List{})
}
func dfsFindPath(root *TreeNode, sum int, countSum int, paths [][]int, path *list.List) [][]int {
if root == nil {
return paths
}
path.PushBack(root.Val)
countSum += root.Val
if root.Left != nil {
paths = dfsFindPath(root.Left, sum, countSum, paths, path)
}
if root.Right != nil {
paths = dfsFindPath(root.Right, sum, countSum, paths, path)
}
if root.Right == nil && root.Left == nil && countSum == sum {
// 遍历链表获取路径
newPath := make([]int, path.Len())
node := path.Front()
for i :=0; node != nil; i++ {
newPath[i] = node.Value.(int)
node = node.Next()
}
paths = append(paths, newPath)
}
path.Remove(path.Back())
return paths
}