题解 | #二叉树中和为某一值的路径(二)#

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param target int整型 
 * @return int整型二维数组
*/
func FindPath( root *TreeNode ,  target int ) [][]int {
    // write code here
  	// 最终的结果切片
    ans := [][]int{}
  	// 存放路径
    path := []int{}
	// 深度优先遍历
    var dfs func(*TreeNode, int) 
    dfs = func(node *TreeNode, target int) {
	  	// 遍历到叶子结点直接返回
        if node == nil {
            return
        }
		// 处理当前节点
        target -= node.Val
        path = append(path, node.Val)
	  	// 如果添加了该节点后满足题目要求（路径必须以叶子节点结尾）
        if node.Left == nil && node.Right == nil && target == 0 {
		  	// path 地址是不变的，不能将 path 直接添加给 ans，否则所有结果中的路径最后都是一样的
            temp := make([]int, len(path))
            copy(temp, path)
            ans = append(ans, temp)
        }
		// 继续处理左右孩子，即使是叶子节点也要走完这个流程，成功将节点弹出 path
        dfs(node.Left, target)
        dfs(node.Right, target)
	  	// 回溯
        path = path[:len(path)-1]
    }

    dfs(root, target)

    return ans
}