描述

输入一颗二叉树的根节点 root 和一个整数 expectNumber，找出二叉树中结点值的和为 expectNumber 的所有路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为 n

如二叉树 root 为 {10,5,12,4,7} ，expectNumber 为 22

         10
        /    \
       5         12
    /  \     
   4    7     

则合法路径有[[10,5,7],[10,12]]

数据范围:

树中节点总数在范围 [0, 5000] 内

-1000 <= 节点值 <= 1000

-1000 <= expectNumber <= 1000

示例

// 输入：
{10,5,12,4,7},22
// 返回值：
[[10,5,7],[10,12]]（返回[[10,12],[10,5,7]]也是对的）

// 输入：
{10,5,12,4,7},15
// 返回值：
[]

// 输入：
{2,3},0
// 返回值：
[]

// 输入：
{1,3,4},7
// 返回值：
[]

解题思路

深度优先搜索

• 维护两个向量ret和path
• 编写递归函数dfs
• 递归函数内部要处理更新path，更新expectNumber，判断是否为叶子节点和判断是否要将path追加到ret末尾

代码示例

var ret [][]int

func dfs(root *TreeNode, expectNumber int, path []int) {
    if nil == root {
        return
    }
    if nil == root.Left && nil == root.Right && root.Val == expectNumber {
        ret = append(ret, append(path, root.Val))
        return
    }
    dfs(root.Left, expectNumber - root.Val, append(path, root.Val))
    dfs(root.Right, expectNumber - root.Val, append(path, root.Val))
}

/**
  * [JZ34-简单] 二叉树中和为某一值的路径(二)
  *
  * @param root TreeNode 类 
  * @param sum int 整型 
  * @return bool 布尔型
*/
func findTreePathSum(root *TreeNode, expectNumber int) [][]int {
    dfs(root, expectNumber, []int{})
    return ret
}