二叉树中和为某一值的路径|博客系列

class Node {
  constructor (value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
/*
* 根据 target 返回某一路径
* param {Tree} tree
* param {Number} target
*/
function searchPath (tree, target) {
    let sum = 0, // 路径上的节点的值的总和
    paths = []; // 存放所有满足条件的路径

    function _searchPath (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) { // 向左子树递归
            _searchPath(node.left, path)
        }
        if (node.right !== null) {
            _searchPath(node.right, path)
        }

        sum = sum - node.value; // 把当前节点从路径中移除, 达到重置的效果
        path.pop();
    }

    _searchPath(tree, []);
    return paths;
}
const tree = new Node(1, new Node(2, new Node(4), new Node(6)), new Node(3, null, new Node(5)));
console.log(searchPath(tree, 9))