树结构中寻找指定元素(根据id之类的唯一标识)的路径

[Rain120]

题目

const data = {
    key: '1',
    id: 'q',
    children: [
        {
            key: '1.1',
            id: 'w',
            children: [
                {
                    key: '1.1.1',
                    id: 'f',
                    children: [],
                },
                {
                    key: '1.1.2',
                    id: 'd',
                    children: [
                        {
                            key: '1.1.2.1',
                            id: 'a',
                            children: [],
                        },
                    ],
                },
            ],
        },
        {
            key: '1.2',
            id: 'x',
            children: [],
        },
        {
            key: '1.3',
            id: 'b',
            children: [],
        },
        {
            key: '1.4',
            id: 'j',
            children: [
                {
                    key: '1.1.2',
                    id: 'k',
                    children: [
                        {
                            key: '1.1.2.1',
                            id: 't',
                            children: [],
                        },
                    ],
                },
                {
                    key: '1.1.2',
                    id: 'i',
                    children: [
                        {
                            key: '1.1.2.1',
                            id: 'o',
                            children: [],
                        },
                    ],
                },
                {
                    key: '1.1.2',
                    id: 'g',
                    children: [
                        {
                            key: '1.1.2.1',
                            id: 'ad',
                            children: [],
                        },
                    ],
                },
            ],
        },
    ],
};

const getPosByIdInTree = (tree, id) => {
   // ...
};

let source = 'ad';
let pos = getPosByIdInTree(data, source);
// ad: 0,3,2,0
console.log(source + ': ' + pos);
source = 'f';
pos = getPosByIdInTree(data, source);
// f: 0,0,0
console.log(source + ': ' + pos);
source = 'x';
pos = getPosByIdInTree(data, source);
// x: 0,1
console.log(source + ': ' + pos);

[Rain120]

const getPosByIdInTree = (tree, id) => {
    const res = [];

    if (tree.id === id) {
        return [0];
    }

    const find = (currentTree, sourceId) => {
        if (currentTree.id === sourceId) {
            res.push(0);
            return;
        }

        if (!currentTree.children) {
            return;
        }

        currentTree.children.forEach((child, index) => {
            if (child.id === sourceId) {
                res.push(index);
                // 回到父级查找
                find(tree, currentTree.id);
            } else {
                // 继续找其他子项
                find(child, sourceId);
            }
        });
    };

    find(tree, id);

    return res.reverse();
};

[Rain120]

衍生题目

从数组中寻找指定元素的路径

const getPosByIdInTree = (tree,id)=>{
    const res = [];

    if (tree.id === id) {
        return [0];
    }

    const find = (currentTree,sourceId)=>{
        if (currentTree.id === sourceId) {
            return;
        }

        if (!currentTree.sub) {
            return;
        }

        currentTree.sub.forEach((child,index)=>{
            if (child.id === sourceId) {
                res.push(index);
                // 回到父级查找
                find(tree, currentTree.id);
            } else {
                // 继续找其他子项
                find(child, sourceId);
            }
        }
        );
    }
    ;

    find(tree, id);

    return res.reverse();
}
;

const findPath = (arr,id)=>{
    arr.forEach((val,i)=>{
        const res = getPosByIdInTree(val, id);
        if (res.length) {
            console.log([i, ...res])
        }
    }
    );
}

测试用例

const data = [
    {
        id: '1',
        sub: [
            {
                id: '2',
                sub: [
                    {
                        id: '3',
                        sub: null,
                    },
                    {
                        id: '4',
                        sub: [
                            {
                                id: '6',
                                sub: null,
                            },
                        ],
                    },
                    {
                        id: '5',
                        sub: null,
                    },
                ],
            },
        ],
    },
    {
        id: '7',
        sub: [
            {
                id: '8',
                sub: [
                    {
                        id: '9',
                        sub: null,
                    },
                    {
                        id: '12',
                        sub: [
                            {
                                id: '128',
                                sub: [
                                    {
                                        id: '129',
                                        sub: null,
                                    },
                                    {
                                        id: '9527',
                                        sub: null,
                                    },
                                ],
                            },
                        ],
                    },
                ],
            },
        ],
    },
    {
        id: '10',
        sub: null,
    },
];

findPath(data, '9527');