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

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

  1.             5
  2.      / \
  3.     4   8
  4.    /   / \
  5.   11  13  4
  6.  /  \    / \
  7. 7    2  5   1
  9. 返回:
  10. [
  11.    [5,4,11,2],
  12.    [5,8,4,5]
  13. ]

提示：节点总数 <= 10000

思路：

  1. dfs

  1. const pathSum = (root, sum) => {
  2.   const result = [];
  4.   const dfs = function (root, path, totalSum) {
  5.     if (!root) return;
  7.     path.push(root.val);
  8.     totalSum += root.val;
  10.     if (!root.left && !root.right) {
  11.       if (totalSum === sum) {
  12.         result.push(path.slice());
  13.       }
  14.     }
  15.     dfs(root.left, path, totalSum);
  16.     dfs(root.right, path, totalSum);
  17.     path.pop();
  18.   }
  20.   dfs(root, [], 0);
  21.   return result;
  22. };
  1. var pathSum = function (root, sum) {
  2.   if (!root) return [];
  3.   const res = [];
  4.   dfs(root, sum, res, []);
  5.   return res;
  6. };
  8. function dfs(root, sum, res, temp) {
  9.   if (!root) return;
  10.   temp.push(root.val); // 1. 选择
  11.   if (!root.left && !root.right && sum === root.val) { // 2. 判断
  12.     res.push([...temp]);
  13.   } else {
  14.     dfs(root.left, sum - root.val, res, temp); // 3. 递归
  15.     dfs(root.right, sum - root.val, res, temp);
  16.   }
  17.   temp.pop(); // 4. 撤销选择
  18. }