当前位置：首页 > news >正文

[面试] js手写题-树转数组

news 2025/7/1 7:08:32

示例数据：

const tree = [{id: 1,name: 'Root',children: [{id: 2,name: 'Child 1',children: [{ id: 4, name: 'Grandchild 1', children: [] }],},{id: 3,name: 'Child 2',children: [],},],},
]

目标生成：

const arr = [{ id: 1, name: 'Root', parentId: null },{ id: 2, name: 'Child 1', parentId: 1 },{ id: 3, name: 'Child 2', parentId: 1 },{ id: 4, name: 'Grandchild 1', parentId: 2 },
]

递归

使用递归遍历树。
在每次递归中记录当前节点的 parentId。
将节点及其子节点逐一添加到结果数组中。

时间复杂度O(n^2)

// 无parentId
function flattenTree(treeList) {let result = []// 遍历当前层级的每个节点treeList.forEach(node => {// 有子节点if (node.children) {// 递归处理子节点，获取当前节点的子节点const childList = flattenTree(node.children)delete node.children;// 将当前节点及其所有子孙节点加入结果数组result.push(node, ...childList)} else {// 没有子节点，即叶子节点result.push({ ...node})}})return result
}const flatData = flattenTree(treeData)

// 有parentId
function flattenTree(treeList, id) {let result = []// 遍历当前层级的每个节点treeList.forEach(node => {// 有子节点if (node.children) {// 递归处理子节点，获取当前节点的子节点const childList = flattenTree(node.children, node.id)delete node.children;// 将当前节点及其所有子孙节点加入结果数组result.push(node, ...childList)} else {// 没有子节点，即叶子节点result.push({ ...node, parentId: id })}})return result
}// 扁平化处理（根节点父ID设为0）
const flatData = flattenTree(treeData, null)

栈深度优先遍历，先进后出

时间复杂度O(n)

// 栈，深度优先遍历，先进后出
function treeToArrayStack(treeList) {const stack = [...treeList]const result = []while (stack.length > 0) {//  当前节点直接pushconst node = stack.pop()result.push({ ...node })// 处理子节点if (node.children) {// 反转子节点数组以保证原始顺序stack.push(...node.children.reverse())//   删除children属性delete result[result.length - 1].children}}return result
}

// 栈，深度优先遍历，先进后出 加上parentId
function treeToArrayStack(treeList) {const stack = [];const result = []// 初始化栈（多个根节点）for (let i = treeList.length - 1; i >= 0; i--) {stack.push({ ...treeList[i], parentId: null });}while (stack.length > 0) {// 当前节点直接pushconst node = stack.pop()result.push({ ...node })// 处理子节点：反向压栈保证顺序if (node.children) {// 反转子节点数组以保证原始顺序const reversedChildren = [...node.children].reverse()reversedChildren.forEach(child => {stack.push({...child,parentId: node.id // 子节点的父ID是当前节点ID})})delete result[result.length - 1].children}}return result
}