深度优先搜索(DFS)算法如何正确回溯？以二叉树查找节点祖先为例

核心错误原因 #

你遇到的问题本质是值传递和引用传递的差异：

• 字符串是值类型，每次传参curr + node.val + '->'都会生成新的字符串，递归各层的字符串互不干扰，所以结果正确。
• 数组是引用类型，所有递归调用共享同一个数组实例，你找到目标后返回的还是这个数组，后续回溯的pop操作会持续修改它，最终导致结果被清空。

原代码的具体问题 #

1. 找到目标后仍执行pop操作：你不管是否找到目标，都会在递归返回前执行curr.pop()，会把已经加入路径的节点逐个删掉，所以最终只剩根节点元素。
2. 返回了共享的数组实例：找到目标时直接返回原数组，后续回溯的修改会直接覆盖正确结果。

正确的回溯实现方案 #

正确的回溯逻辑要满足两个核心规则：

• 找到目标节点后直接终止回溯，不执行撤销操作
• 只有当前节点的左右子树都没有匹配到目标时，才执行pop撤销当前节点的选择

修正后代码示例 #

var ancestor = function(root, target) {
    const result = [];
    const dfs = (node, currPath) => {
        if (node === null) return false;
        // 把当前节点加入路径
        currPath.push(node.val);
        // 匹配到目标节点，保存当前路径副本
        if (node.val === target.val) {
            result.push(...currPath);
            return true;
        }
        // 左子树找到就直接返回，不执行撤销
        if (dfs(node.left, currPath)) return true;
        // 右子树找到就直接返回，不执行撤销
        if (dfs(node.right, currPath)) return true;
        // 左右子树都没找到，撤销当前节点的选择
        currPath.pop();
        return false;
    }
    dfs(root, []);
    console.log(result);
};

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