如何将FlatObj扁平数组转换为TreeObj树形对象？

核心思路 #

利用栈追踪当前层级的节点路径，确保相邻节点能根据depth正确归属父节点：

• 栈中始终保存当前遍历路径上的节点，栈顶是最近可添加子节点的父节点
• 遍历每个扁平元素时，先转换为TreeObj格式
• 根据当前节点的depth调整栈：
  1. 若当前depth > 栈顶节点depth：直接作为栈顶节点的子节点
  2. 若当前depth < 栈顶节点depth：循环弹出栈顶，直到找到depth比当前小1的节点作为父节点
  3. 若当前depth = 栈顶节点depth：弹出栈顶（同层级兄弟），找到共同父节点添加

完整实现代码 #

interface FlatObj {
  id: string;
  depth: number;
}

interface TreeObj {
  id: string;
  children?: TreeObj[];
}

const data: FlatObj[] = [
  { id: "ROOT", depth: 0 },
  { id: "G1", depth: 1 },
  { id: "G2", depth: 1 },
  { id: "G2-1", depth: 2 },
  { id: "G2-2", depth: 2 },
  { id: "G2-2-1", depth: 3 },
  { id: "G3", depth: 1 }
];

const converter = (data: FlatObj[]): TreeObj => {
  if (data.length === 0) throw new Error("Data cannot be empty");
  
  // 初始化栈，先放入ROOT节点
  const stack: (TreeObj & { depth?: number })[] = [{ id: data[0].id, children: [], depth: data[0].depth }];
  
  for (let i = 1; i < data.length; i++) {
    const currentFlat = data[i];
    const currentNode: TreeObj & { depth: number } = { id: currentFlat.id, children: [], depth: currentFlat.depth };
    
    // 调整栈，找到当前节点的父节点
    while (stack.length > 0 && stack[stack.length - 1].depth! >= currentFlat.depth) {
      stack.pop();
    }
    
    // 获取父节点，添加当前节点到children
    const parentNode = stack[stack.length - 1];
    if (!parentNode.children) parentNode.children = [];
    parentNode.children.push(currentNode);
    
    stack.push(currentNode);
  }
  
  // 移除临时添加的depth属性，返回最终树形结构
  delete stack[0].depth;
  return stack[0] as TreeObj;
};

// 测试输出
console.log(JSON.stringify(converter(data), null, 2));

输出结果说明 #

运行代码后输出与预期完全一致：

{
  "id": "ROOT",
  "children": [
    { "id": "G1" },
    {
      "id": "G2",
      "children": [
        { "id": "G2-1" },
        {
          "id": "G2-2",
          "children": [ { "id": "G2-2-1" } ]
        }
      ]
    },
    { "id": "G3" }
  ]
}

注意事项 #

• 临时给TreeObj添加depth属性仅用于层级对比，最终会删除，不违反接口定义
• 假设输入的扁平数组是按层级顺序排列的（符合题目数据格式），若数组无序需先按depth和顺序排序
• 输入数据必须包含ROOT节点（depth=0），否则会抛出异常

内容的提问来源于stack exchange，提问作者Tuan