树的递归和回溯问题

[AILINGANGEL]

题目1：找到在这个树中满足某个条件的节点，满足这个条件的节点是唯一的，返回从根节点到这个节点的路径

// 找到到达某个节点的路径, 满足这个条件的节点是唯一的
export function findPathToNode(root, targetId, ans = [], childrenLabel = 'children') {
    if (root === null) {return false;}
    if (root.id === targetId) {
        ans.push(root.id);
        return true;
    }
    let children = root[childrenLabel];
    if (children) {
        ans.push(root.id);
        for (let i = 0; i < children.length; i++ ) {
            let isFind = findPathToNode(children[i], targetId, ans, childrenLabel);
            if (isFind) {
                return true;
            }
        }
        ans.pop();
    }
    return false;
}

题目2：在这个树上找到所有满足某个条件的节点，且返回到这些节点的路径（或者去除到不满足条件的节点的所有路径），有可能子节点a满足条件，子节点的子节点b也满足条件，需要返回到b的这条路径

export function findInTreeTable(node, target, cb, flag, childrenLabel = 'children') {
    if (node) {
        if (cb(node, target)) {
            flag.isFound = true;
        }
        let children = node[childrenLabel];
        if (children) {
            let flags = [];
            let found = false;
            for (let i = 0; i < children.length; i++) {
                flags.push({ isFound: false });
                findInTreeTable(children[i], target, cb, flags[i], childrenLabel);
                if (flags[i].isFound) {
                    found = true;
                }
            }
            if (!found) {
                node[childrenLabel] = null;
            } else {
                flag.isFound = true;
                node[childrenLabel] = node[childrenLabel].filter((item, index) => flags[index].isFound);
            }
        }
    }
}