面试：扁平数据结构转Tree

题目

扁平的数据结构，转成树。
打平的数据内容如下：

let arr = [
    {id: 1, name: '部门1', pid: 0},
    {id: 2, name: '部门2', pid: 1},
    {id: 3, name: '部门3', pid: 1},
    {id: 4, name: '部门4', pid: 3},
    {id: 5, name: '部门5', pid: 4},
]
````
输出结果

[
{
“id”: 1,
“name”: “部门1”,
“pid”: 0,
“children”: [
{
“id”: 2,
“name”: “部门2”,
“pid”: 1,
“children”: []
},
{
“id”: 3,
“name”: “部门3”,
“pid”: 1,
“children”: [
// 结果 ,,,
]
}
]
}
]

## 递归遍历查找
主要思路是提供一个递getChildren的方法，该方法递归去查找子集。

/**

• 递归查找，获取children
• /
  const getChildren = (data, result, pid) => {
  for (const item of data) {
  if (item.pid === pid) {

  const newItem = {...item, children: []};
  result.push(newItem);
  getChildren(data, newItem.children, item.id);
  

  }
  }
  }

/**

• 转换方法
• /
  const arrayToTree = (data, pid) => {
  const result = [];
  getChildren(data, result, pid)
  return result;
  }

时间复杂度为`O(2^n)`。
## map转换
主要思路是先把数据转成Map去存储，之后遍历的同时借助对象的引用，直接从Map找对应的数据做存储;

function arrayToTree(items) {
const result = []; // 存放结果集
const itemMap = {}; //

// 先转成map存储
for (const item of items) {
itemMap[item.id] = {…item, children: []}
}

for (const item of items) {
const id = item.id;
const pid = item.pid;
const treeItem = itemMap[id];
if (pid === 0) {
result.push(treeItem);
} else {
if (!itemMap[pid]) {
itemMap[pid] = {
children: [],
}
}
itemMap[pid].children.push(treeItem)
}

}
return result;
}

时间复杂度为`O(2n)`，需要一个Map把数据存储起来，空间复杂度`O(n)`
## 再次优化

function arrayToTree(items) {
const result = []; // 存放结果集
const itemMap = {}; //
for (const item of items) {
const id = item.id;
const pid = item.pid;

if (!itemMap[id]) {
  itemMap[id] = {
    children: [],
  }
}

itemMap[id] = {
  ...item,
  children: itemMap[id]['children']
}

const treeItem =  itemMap[id];

if (pid === 0) {
  result.push(treeItem);
} else {
  if (!itemMap[pid]) {
    itemMap[pid] = {
      children: [],
    }
  }
  itemMap[pid].children.push(treeItem)
}

}
return result;
}