二叉树中和为某一值的路径

思路——动态规划（应该算吧？）

要点

• 辅助函数
• 假设知道前面节点的路径数组pre
• 用一个二维数组resArr保存所有路径

判断逻辑

情况1、如果当前节点 == null，或其值 > 期待值

那么就不用继续遍历下去了，return。

情况2、如果当前节点的值 == 期待的值，并且当前节点是叶子节点

那么就找到了一个路径，将当前节点的值加入pre（之前的路径数组），再将pre加入我们的结果resArr中。

情况3、以上情况都不满足

说明还可以继续找下去。就更新参数，对其左右子节点递归。

代码

function FindPath(root, expectNumber)
{
    // write code here
    // 保存路径结果
    var resArr = [];
    // 前序遍历，递归查找
    nextLayer(root, expectNumber, [], resArr);
    // 让数组长度大的靠前。（不做处理好像也通过测试了，不过还是按题意来得好）
    resArr.sort(function(a, b){
        return b.length - a.length;
    });
    return resArr;
}
function nextLayer(node, exp, pre, resArr){
    // 情况1
    if(node==null || node.val > exp){
        return;
    }
    // 注意对过期路径做拷贝，因为左右子节点都需要使用，不能互相影响
    var cur = pre.slice(0);
    cur.push(node.val);
    // 情况2
    if(node.val == exp && node.left==null && node.right==null){
        resArr.push(cur);
        return;
    }
    // 情况3。注意更新参数
    nextLayer(node.left, exp-node.val, cur, resArr);
    nextLayer(node.right, exp-node.val, cur, resArr);
}