题目描述

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

样例

给出二叉树如下所示，并给出num=22。
      5
     / \
    4   6
   /   / \
  12  13  6
 /  \    / \
9    1  5   1

输出：[[5,4,12,1],[5,6,6,5]]

golang 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 //定义全局变量
var ans [][]int
func findPath(root *TreeNode, sum int) [][]int {
    if root == nil {
        return nil
    }
    var a []int
    //深度优先遍历
    dfs(root, sum, a)
    return ans
}

func dfs(root *TreeNode, sum int, a []int) {
    //添加节点到路径slice
    a = append(a, root.Val)
    //子节点不为空，向下遍历
    if root.Left != nil {
        dfs(root.Left, sum, a)
    }
    if root.Right != nil {
        dfs(root.Right, sum, a)
    }
    //找到子节点，判断
    if root.Left == nil && root.Right == nil{
        var t []int
        //此处添加t而不是直接append切片a，是因为append切片是添加切片指针，后续切片改变会影响ans结果
        var temp int
        for _,i := range a {
            temp += i
            t = append(t,i)
        }
        if temp == sum {
            ans = append(ans,t)
        }
    }
}