剑指offer[24]——二叉树中和为某一值的路径

题目描述

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

这道题目的思路比较简单，大家可以想一下，如果我们手动去做这道题的话，是怎么做的呢，就是先把所有的路径都数出来，然后再筛选所有符合条件的路径，存储在一个数组中，然后再按数组长度进行排序。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function FindPath(root, expectNumber) {
    if(!root){return [];}
  let allRoutes = [];
  function sum(arr) {
    let _sum = 0;
    for(let item of arr){
      _sum += item;
    }
    return _sum;
  }
  function findRoute(_root, route) {
    let _route = route.slice(0);
    _route.push(_root.val);
    if (_root.left) { findRoute(_root.left, _route); }
    if (_root.right) { findRoute(_root.right, _route); }
    if (!_root.left && !_root.right) { allRoutes.push(_route); }
  }
  let r = [];
  findRoute(root, r);
  return allRoutes.filter(item => {
    return sum(item) == expectNumber;
  });
}