数组转树

题目

定义一个 convert 函数，将以下数组转换为树结构。

const arr = [
    { id: 1, name: '部门A', parentId: 0 }, // 0 代表顶级节点，无父节点
    { id: 2, name: '部门B', parentId: 1 },
    { id: 3, name: '部门C', parentId: 1 },
    { id: 4, name: '部门D', parentId: 2 },
    { id: 5, name: '部门E', parentId: 2 },
    { id: 6, name: '部门F', parentId: 3 },
]

分析

定义树节点的数据结构

interface ITreeNode {
    id: number
    name: string
    children?: ITreeNode[]
}

遍历数组，针对每个元素

• 生成 tree node
• 找到 parentNode 并加入到它的 children

找 parentNode 时，需要根据 id 能尽快找到 tree node
需要一个 map ，这样时间复杂度是 O(1) 。否则就需要遍历查找，时间复杂度高。

实现

/**
 * @description array to tree
 * @author 双越老师
 */

interface IArrayItem {
    id: number;
    name: string;
    parentId: number;
}

interface ITreeNode {
    id: number;
    name: string;
    children?: ITreeNode[];
}

function convert(arr: IArrayItem[]): ITreeNode | null {
    // 用于 id 和 treeNode 的映射
    const idToTreeNode: Map<number, ITreeNode> = new Map();

    let root = null;

    arr.forEach((item) => {
        const { id, name, parentId } = item;

        // 定义 tree node 并加入 map
        const treeNode: ITreeNode = { id, name };
        idToTreeNode.set(id, treeNode);

        // 找到 parentNode 并加入到它的 children
        const parentNode = idToTreeNode.get(parentId);
        if (parentNode) {
            if (parentNode.children == null) parentNode.children = [];
            parentNode.children.push(treeNode);
        }

        // 找到根节点
        if (parentId === 0) root = treeNode;
    });

    return root;
}

const arr = [
    { id: 1, name: "部门A", parentId: 0 }, // 0 代表顶级节点，无父节点
    { id: 2, name: "部门B", parentId: 1 },
    { id: 3, name: "部门C", parentId: 1 },
    { id: 4, name: "部门D", parentId: 2 },
    { id: 5, name: "部门E", parentId: 2 },
    { id: 6, name: "部门F", parentId: 3 },
];
const tree = convert(arr);
console.info(tree);

扩展

这两种数据结构很像 MySQL vs Mongodb ，一个关系型，一个文档型