为什么使用此代码执行 DFS 会导致重复叶子？

Question

我正在编写一个算法来辨别两棵树是否具有相同的叶子。

它们具有相同顺序的相同叶子编号，因此返回 true。

这是我写的代码：

function leafSimilar(root1: TreeNode | null, root2: TreeNode | null): boolean {

    console.log(DFS(root1))

    const leavesRoot1 = DFS(root1);
    const leavesRoot2 = DFS(root2);

    for (let i = 0; i < Math.max(leavesRoot1.length, leavesRoot2.length); i += 1) {
        if (leavesRoot1[i] !== leavesRoot2[i]) {
            return false;
        }
    }

    return true;
};

function DFS(root, leaves = [] ) {

    if(!root) return leaves; 

    if (!root.left && !root.right) {
        leaves.push(root.val);
        return leaves;
    }

    // return DFS(root.left).concat(DFS(root.right)); // this is the correct answer

    return DFS(root.left, leaves).concat(DFS(root.right, leaves)); // why doesn't this work?
}

代码中的最后一行是我最初的想法，但它是错误的。

我无法在脑海中画出它，所以我将它们记录下来，如第二行所示。

它记录：

[
  6, 7, 4, 
  6, 7, 4, 
  6, 7, 4, 
  6, 7, 4, 9, 8,
  6, 7, 4, 9, 8
] 

2个小时后，我不明白这是为什么。

我认为它至少应该是类似的东西：

[6, 
 6, 7, 
 6, 7, 4, 
 6, 7, 4, 9,
 6, 7, 4, 9, 8,
]

或者只是

[6,7,4,9,8]

哪个是正确的。

有人可以向我解释一下为什么吗？

DFS

函数从之前的调用中获取

leaves

数组参数。

这意味着它应该从上面的节点接收

leaves

，而不是下面的节点，因此

leaves

数组中不应该有重复模式，因为它是空的。

根据我编写的代码，DFS 是预先排序的，因此首先评估最左边的节点。

请帮我理解。

Answer 1

如果你这样做的话，你的方法就会有效：

    DFS(root.left, leaves);
    DFS(root.right, leaves);
    return leaves;

这里我们忽略由DFS返回的数组

。意识到当第一个递归调用返回时， 

leaves

 具有来自左子树的一些值。第二个递归调用使用更多值

扩展此数组。正确的做法是在第二次人口发生后返回leaves

。

请注意，

DFS

返回对

values

数组的引用，因此本质上每个调用都会返回

same引用。如果你这样做 values.concatenate(values)

 很明显你重复了值，但这正是你正在做的事情：

DFS(root.left, leaves).concat(DFS(root.right, leaves)); 它只是有点晦涩......因为

values

 在两个递归调用中都被填充。但这与解释问题完全无关。关键的理解是两个递归调用都返回对同一数组的引用。

为了避免此类问题，最好的做法是

从不让函数返回对也作为参数传递的对象的引用，并且该对象会发生变化。最好在这两种模式之间进行选择：

• 让函数将对象（在本例中为数组）作为参数，但返回未定义。这样，调用者就会更加意识到他们的论点已经发生了变化。

• 让函数

  not将对象作为参数，但让它从头开始构造一个对象，然后将其返回给调用者。在此模式中，函数的每次调用都会返回一个不同的对象引用。

混合这两种模式很容易导致您遇到的问题。在这个实际的算法中，我对第二种模式有明显的偏好，那么就不应该有

values

 的争论。所以：

function DFS(root) {
    if (!root) return []; 
    if (!root.left && !root.right) return [root.val];
    return DFS(root.left).concat(DFS(root.right));
}