为什么递归不处理变量的状态

Question

这是一个查找树从根到叶的所有路径的代码。 输入

class Node {
    constructor (val) {
        this.val   = val;
        this.left  = null;
        this.right = null; 
    }
}

const a = new Node('10');
const b = new Node('20');
const c = new Node('30');
const d = new Node('40');
const e = new Node('60');


a.left = b;
a.right = c;
b.left = d;
b.right = e;

function Paths(root){
        let paths = [];
        function traverse(node, path){
            if(!node){
                return;
            }
            path.push(node.val);
            if(node.left ==null && node.right ==null){
                paths.push(path.slice());
            }
            traverse(node.left,path);
            traverse(node.right,path);
            path.pop();
        }
        traverse(root,[]);
        console.log(paths);
        return paths;
    }
    Paths(a);

我知道我需要回溯，以便删除最后一个元素（弹出）并返回到原始状态。 但是，当我在递归调用中共享 path 变量时，递归不应自行处理路径在特定节点时的值是什么 对于第一条路径 10,20,40，当我再次移回节点右侧的 20 时，路径变量的值当时不应该是 10,20 吗？

vs 我们不需要任何回溯 给定二叉树的根和整数 targetSum，如果树具有从根到叶的路径，使得沿路径的所有值相加等于 targetSum，则返回 true。

叶子是没有子节点的节点。

class Node {
    constructor (val) {
        this.val   = val;
        this.left  = null;
        this.right = null; 
    }
}

const a = new Node('1');
const b = new Node('2');
const c = new Node('3');
a.left = b;
a.right = c;


var hasPathSum = function(root, targetSum) {
    if(!root){
        return 0;
    }
    function dfs(node, currsum){
        if(!node){
            return false;
        }
        currsum+=Number(node.val);
        //
        if(node.left ==null && node.right ==null){
            return currsum == targetSum;
        }

        return dfs(node.left,currsum) || 
        dfs(node.right,currsum);
    }
    return dfs(root, 0);
};

let targetSum =31;
console.log(hasPathSum(a, targetSum));

Answer 1

这是编写代码的更简单方法：

class Node {
  constructor (val) {
    this.val = val;
  }
}

const a = new Node('10');
const b = new Node('20');
const c = new Node('30');
const d = new Node('40');
const e = new Node('60');

a.left = b;
a.right = c;
b.left = d;
b.right = e;

const f = n => (n.left || n.right) ?
  [n.left, n.right].filter(i=>i).flatMap(i=>f(i))
  .map(p => [n.val, ...p]) : [[n.val]]


console.log(f(a))

如果是叶子，则返回包含一条路径的列表。

否则，递归生成左侧和右侧的所有不同路径，并使用

map

将我们的节点值添加到每个路径。