JS实现深度优先搜索

const { isEmpty, find } = require('lodash');
const Tree = [
    {
        id: 1,
        parent: 0,
        children: [
            {
                id: 2,
                parent: 1,
            },
            {
                id: 3,
                parent: 1,
                children: [
                    {
                        id: 4,
                        parent: 3,
                    },
                    {
                        id: 5,
                        parent: 3,
                    },
                    {
                        id: 6,
                        parent: 3,
                        children: [
                            {
                                id: 7,
                                parent: 6,
                                children: [
                                    {
                                        id: 8,
                                        parent: 7,
                                    },
                                    {
                                        id: 9,
                                        parent: 7,
                                    },
                                ]
                            },
                            {
                                id: 10,
                                parent: 6
                            }
                        ]
                    },
                ]
            },
        ]
    }
];

const depthFirstSearch = (tree, condition, primaryKey) => {
    if (isNil(tree) || isNil(condition)) {
        return null;
    }
    const visitedNodeKeys = [];
    const stack = [];
    if (condition(tree[0])) {
        return tree[0];
    } else {
        visitedNodeKeys.push(tree[0][primaryKey]);
        stack.push(tree[0]);
    }
    while (!isEmpty(stack)) {
        const lastIndex = stack.length - 1;
        const endItem = stack[lastIndex];
        const endItemChildren = endItem.children || [];
        const notVisitedChild = find(endItemChildren, child => !some(visitedNodeKeys, key => isEqual(child[primaryKey], key)));
        if (notVisitedChild) {
            if (condition(notVisitedChild)) {
                return notVisitedChild;
            } else {
                visitedNodeKeys.push(notVisitedChild[primaryKey]);
                stack.push(notVisitedChild);
            }
        } else {
            stack.pop();
        }
    }
    return null;
};

console.log(depthFirstSearch (Tree , element => element.id === 9, 'id')));