路径总和 II-113

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

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

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

典型的可以用 DFS 来解决的问题，定义一个 search 方法并且参数里带一个用来收集路径的 paths 数组，每当到达叶子节点（没有 left 也没有 right），就计算一把路径的总和，如果等于目标值就 push 到结果数组里。（注意这里要浅拷贝一下，防止下面的计算污染这个数组）

任何一个节点处理完成时，都要把当前节点 pop 出 paths 数组。

let pathSum = function (root, sum) {
  let res = [];
  let search = function (node, paths) {
    if (isInvalid(node)) return;
    paths.push(node.val);
    if (node.left) {
      search(node.left, paths);
    }
    if (node.right) {
      search(node.right, paths);
    }
    if (!node.left && !node.right) {
      if (sumVals(paths) === sum) {
        res.push(paths.slice());
      }
    }
    paths.pop();
  };
  search(root, []);
  return res;
};

function sumVals(nodes) {
  return nodes.reduce((prev, val) => {
    prev += val;
    return prev;
  }, 0);
}

function isInvalid(node) {
  return !node || node.val === undefined || node.val === null;
}