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

# 1. 题目描述

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

# 2. 思路分析

1. 每次来到新的节点，记录新节点信息
2. 检查新节点是否是叶子节点，如果是，判断路径上的节点值总和是否符合条件；如果不是，继续递归处理左右子树，回到第 1 步
3. 最后需要将新节点的信息移除

# 3. 代码实现

/**
 * 二叉树结点类
 */
class Node {
  constructor(value = 0, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

/**
 *
 * @param {Node} root
 * @param {Number} target
 */
function findPath(root, target) {
  const paths = []; // 存放所有满足条件的路径
  let sum = 0; // 路径上的节点值的总和

  function _findPath(node, path) {
    if (node === null) {
      return;
    }

    // 把当前节点放入路径中
    sum = sum + node.value;
    path.push(node);

    const isLeaf = node.left === null && node.right === null;

    // 如果是叶节点, 并且路径上的节点和满足条件, 记录这条路径
    if (isLeaf && sum === target) {
      paths.push([...path]);
    }

    // 当前节点有左子树, 向左子树递归
    if (node.left !== null) {
      _findPath(node.left, path);
    }

    // 当前节点有右子树, 向右子树递归
    if (node.right !== null) {
      _findPath(node.right, path);
    }

    // 把当前节点从路径中移除
    sum = sum - node.value;
    path.pop(node);
  }

  _findPath(root, []);
  return paths;
}

/**
 * 以下是测试代码
 */
const root = new Node(1, new Node(2), new Node(3, null, new Node(-1)));

console.log(findPath(root, 3));