常见算法题

偏平数据结构转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": [
                    // 结果 ,,,
                ]
            }
        ]
    }
]

时间复杂度

时间复杂度的计算并不是计算程序具体运行时间,而是算法执行语句的次数。

计算方法

1. 选取相对增长最高的项
2. 最高项系数都为1
3. 若是常数的话用O(1)表示

   空间复杂度

   递归实现

   ``` /**
   • 递归查找，获取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; }

<a name="SJnrM"></a>
### 递归实现总结
1. data 原数据 result 保存结果 pid 根id
2. getChildren(data,result,pid)
3. 遍历data  把 item.pid = pid   保存到 result
4. 递归调用 getChildrenI(data,item.children,item.id)
<a name="mQpIc"></a>
### 不用递归
<a name="oHHEZ"></a>
#### 主要思路:
先把数据转成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; }

<a name="jyayU"></a>
#### 思路总结
items  原数据   result 处理后的对象
1. 先把 items数据，根据 id 转为 Map
2. 循环 items  id = 0 保存到 result      其他在 Map 里面找到对应父级,添加到children中
3. 到最后 pid = 0 也会被添加children
<a name="mFEVK"></a>
### 最优解

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; }

```