为何此DFS代码会生成重复叶子节点？求技术解析

我正在实现一个判断两棵二叉树是否具有相同叶子节点的算法（叶子节点顺序和数值相同时返回true），但编写的DFS代码出现了重复叶子节点的问题，以下是代码：

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
]

我原本预期得到以下两种结果之一：

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

或

[6,7,4,9,8]

正确写法是注释中的return语句，恳请帮忙解释错误写法导致重复叶子的原因。

问题原因解析 #

核心问题在于你复用了同一个leaves数组引用，并且在concat操作中重复拼接了这个已被修改的数组：

1. DFS函数的默认参数leaves = []会在第一次调用时创建一个空数组，后续递归调用如果传入这个数组，所有操作都会基于同一个数组实例。
2. 遍历左子树时，叶子节点值会被push进这个leaves数组，返回的是该数组的引用；接着遍历右子树时，同样往这个数组里添加叶子值，返回的还是同一个引用。
3. 执行leftResult.concat(rightResult)时，本质是把同一个数组和它自身拼接，直接导致内容重复。
4. 递归过程中每一次concat都会重复拼接这个被多次修改的数组，最终就出现了日志里多次重复的叶子序列。

而正确写法return DFS(root.left).concat(DFS(root.right))的逻辑是：

• 调用DFS(root.left)时，未传入leaves参数，会创建新的空数组收集左子树叶子；调用DFS(root.right)同理，也会创建新数组收集右子树叶子。
• 最后合并两个独立的数组，得到完整且无重复的叶子序列。

内容的提问来源于stack exchange，提问作者Joon K