JS实现嵌套树节点路径查找时路径拼接错误如何修复

问题根源 #

你的代码核心问题是使用了外部作用域的currentPath变量存储拼接路径，当递归遍历完某个非目标节点的子树后，没有回退已经追加到路径中的当前节点名，导致前面遍历过的节点名残留在最终路径里。比如遍历src节点时你把/src拼到了路径里，src子树没找到目标时你没有把这部分内容删掉，后面找到index.html的时候就会多出来/src前缀。

修复方案 #

方案1：增加路径回溯逻辑（基于原有代码最小改动） #

在递归调用子树未找到目标时，回退currentPath到追加当前节点名之前的状态即可：

const getFSNodePath = (tree: Array<FSNode>, targetNode: FSNode) => {
    let currentPath = '';
    
    function buildPath(subTree: Array<FSNode>, targetNode: FSNode): string | undefined{
        for(const node of subTree){
            // 遍历所有节点，查找和目标匹配的节点
            if(node.id === targetNode.id){
                // 将目标节点名追加到路径末尾
                currentPath = currentPath + '/' + node.name;
                return currentPath;
            } else if(node.children){
                // 记录追加前的路径长度，用于后续回溯
                const prevPathLen = currentPath.length;
                // 存在子节点则递归查询子树，递归查询前先将当前节点名加入路径
                currentPath = currentPath + '/' + node.name;

                const path = buildPath(node.children, targetNode);
                // 查到路径时直接返回
                if(path) return path;
                // 子树未查到目标，回退路径到追加当前节点前的状态
                currentPath = currentPath.slice(0, prevPathLen);
            }
        }
    }

    const path = buildPath(tree, targetNode);
    return path;
};

方案2：递归传参（更推荐，无副作用） #

不使用外部变量存储路径，而是把当前拼接的路径作为递归参数传递，天然避免回溯问题，逻辑更清晰：

const getFSNodePath = (tree: Array<FSNode>, targetNode: FSNode) => {
    function buildPath(subTree: Array<FSNode>, prefix: string): string | undefined{
        for(const node of subTree){
            const currentPath = `${prefix}/${node.name}`;
            if(node.id === targetNode.id) return currentPath;
            if(node.children){
                const childPath = buildPath(node.children, currentPath);
                if(childPath) return childPath;
            }
        }
    }
    return buildPath(tree, '');
};

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