题目描述：

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22，

  1.           5<br />             / \<br />            4   8<br />           /   / \<br />          11  13  4<br />         /  \    / \<br />        7    2  5   1<br />返回:

[
[5,4,11,2],
[5,8,4,5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof

知识点：

  • 深度优先遍历，回溯

解题思路：

  • 这道题是一个典型的深度优先遍历加回溯的问题
  • 深度优先遍历中我们将遇见的子节点不断的放入一个数组中，当走到叶节点时，我们需要判断当前数组里的元素和是否为要求的目标和（在递归中不断用目标和减去当前的节点值）
  • 当达到的时候我们需要将数组中的所有元素放入到我们的path路径数组中便好
  • 注意在走到叶节点时我们一定要将数组中的最后一个元素删除，来达到回溯的目的

解题代码：

function FindPath(root, expectNumber)
{
    // write code here
    if(!root) return [];
    const path = [];
    const res = [];
    rec(root, expectNumber);
    return path;
    function rec(node,expN){
        res.push(node.val);
        if(node.val === expN && !node.left && !node.right) {
            path.push(res.slice(0));
        }else {
            if(node.left) rec(node.left,expN - node.val);
            if(node.right) rec(node.right,expN - node.val);
        }
        // 要去查找其他的路径上的节点了就将当前节点删除掉
        // 最后如果没有找到res其实是空的
        res.pop(); 
    }
}