javascript - 将带有级别信息的平面数组重新排列成带有子节点的 n 叉树

Question

给定一个层次格式的数组，它们的直接子级存储在一个连续的数组中，返回一个 n 叉树

给定输入格式:

[{'name':'a', 'level': -1},
    {'name':'b', 'level': 0},
        {'name':'c', 'level': 1},
            {'name':'d', 'level': 2},
    {'name':'e', 'level': 0},
        {'name':'f', 'level': 1},
    {'name':'g', 'level': 0}
];

预期输出应采用以下格式:

[
 {
  name:"a",
  level:-1,
  children: [
    {
      name:"b",
      level:0,
      children: [
         {
           name:"c",
           level:1,
           children: [
              {
                  name:"d",
                  level:2,
                  children: [ ]
              }
            ]
         }
       ]
    }
  ],
 },
 {
   name:"e",
   level:1,
   children: [
        {
          name:"f",
          level:2,
          children: [ ]
        }
   ]
 },
 {
   name:"g",
   level:2,
   children: [ ]
 }
]

我尝试实现的递归解决方案失败了

以上代码返回

function treeTraversal(arr, index) {
  if (arr === null || arr.length === 0 || index === arr.length) {
    return;
  }

  let result = [];
  let children = [];
  if (arr[index - 1].level + 1 === arr[index].level) {
    children.push(arr[index]);
    console.log(children);
    treeTraversal(arr, index + 1);
  }
  arr[index - 1].children = children;
  result.push(arr[index - 1]);
  return result;
}

const arr = [{
    'name': 'a',
    'level': -1
  },
  {
    'name': 'b',
    'level': 0
  },
  {
    'name': 'c',
    'level': 1
  },
  {
    'name': 'd',
    'level': 2
  },
  {
    'name': 'e',
    'level': 0
  },
  {
    'name': 'f',
    'level': 1
  },
  {
    'name': 'g',
    'level': 0
  }
];

console.log(treeTraversal(arr, 1));

意想不到的结果。请让我知道上面的代码有什么问题

Answer 1

您可以为关卡获取一个辅助数组，并将对象分配给该关卡的最新数组加一。

var data = [{ name: 'a', level: -1 }, { name: 'b', level: 0 }, { name: 'c', level: 1 }, { name: 'd', level: 2 }, { name: 'e', level: 0 }, { name: 'f', level: 1 }, { name: 'g', level: 0 }],
    tree = [],
    levels = [tree];

data.forEach(o => levels[o.level + 1].push({ ...o, children: levels[o.level + 2] = [] }));

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }