请用 JavaScript 编写一个函数,实现将扁平对象数组转换为树形结构的功能,并给出具体实现代码。
考察说明
考查对树形结构转换算法及 JavaScript 数组、对象操作能力的掌握程度。
回答思路
- 【回答框架 1】先明确转换前提:扁平数组中每个对象包含唯一的 id 和 parentId 字段,parentId 为 null 或不存在时表示根节点。采用一次遍历加两次循环的算法,先构建 id 到节点的映射,再遍历数组,将每个节点挂到其父节点的 children 数组中,若为根则放入结果数组。
- 【回答框架 2】具体步骤:先初始化一个空的 Map 或对象用于存储 id 到节点引用的映射。第一遍遍历数组,将每个节点的 children 初始化为空数组,并存入映射。第二遍遍历,对于每个节点,查找其 parentId 对应的父节点,若存在则将该节点推入父节点的 children,否则作为根节点加入结果数组。这样一次遍历即可完成,时间复杂度为 O(n)。
- 【回答框架 3】边界处理:需要处理 parentId 指向不存在节点的情况,此时按根节点处理或根据需求忽略。若原数组顺序不定,映射方式可保证正确挂载。提供完整代码示例,包括测试用例,检查根节点和嵌套层级输出是否符合预期。
- 【回答框架 4】复杂度分析:时间 O(n),空间 O(n)。说明该算法避免了递归或重复查找,适合大数据量场景。
- 【关键点 1】使用 Map 或对象构建 id 到节点的映射,避免多次查询父节点。
- 【关键点 2】一次遍历即可完成挂载,时间复杂度 O(n),空间复杂度 O(n)。
- 【关键点 3】注意处理根节点(parentId 为 null)和缺失父节点的情况。
- 【易错点 1】若父节点未在数组中定义,直接忽略会导致子节点丢失,应明确处理策略。
- 【易错点 2】避免使用递归查找父节点,否则时间复杂度可能退化为 O(n^2)。