今天这个题目说起来不算太复杂，不过在面试中遇到的频率还比较高，而且面试过程中手写时，不少人在规定的时间内写不出来。

如何把一个 扁平 的数据结构，转换成一棵 树 的结构。

题目如下：

// 扁平的数据内容如下：后端返回的部门数据，可能直接从数据库查出来的，是扁平的。每个部门的上一级部门，用 pid 关联
const 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},
]
// 实现一个函数 list2tree(arr) 
const tree = list2tree(arr);
// tree 的数据如下
[
 {id: 1, name: '部门1', pid: 0, 
  children: [
    {id: 2, name: '部门2', pid: 1, children: []},
    {id: 3, name: '部门3', pid: 1, children: [
      {id: 4, name: '部门4', pid: 3, children: [
        {id: 5, name: '部门5', pid: 4, children: []}
      ]}
    ]}
  ]
 }
]

解题思路

对比扁平的JSON和处理之后的树形数据，可以看到每个部门都是一个节点，每个节点通过 children 数组来包含子节点（下级部门）。

我们只需要遍历原始扁平的数据，在遍历过程中，根据每个节点的 pid 找到他的父级节点，把当前节点放到父级节点的 children 数组里即可。

需要注意的是，pid===0的部门是顶级部门，没有上级部门。

解题过程

1. 实现函数输入和输出签名

function list2tree(arr) {
  const out = [];
  // 中间逻辑
  return out;
}

2. 开始填充逻辑。在遍历过程中，要把当前节点放到父节点的 children 里，但是有可能先遍历的是子节点，因此需要用额外的一个 Map ，存储某个节点对应的子节点数组

function list2tree(arr) {
  const out = [];
  // 存储 id => children 的映射
  const idChildrenMap = new Map();
  arr.forEach((obj) => {
    // 下面处理把当前节点，放到父节点的 children 里
    let parentChildrenList = idChildrenMap.get(obj.pid);
    if (!parentChildrenList) {
      parentChildrenList = [];
      idChildrenMap.set(obj.pid, parentChildrenList);
    }
    // 新生成一个数据，不去修改 arr 里的数据
    const newNode = {
      id: obj.id,
      pid: obj.pid,
      name: obj.name,
      // 优先从映射缓存里，读取当前节点的子节点
      children: idChildrenMap.get(obj.id),
    };
    parentChildrenList.push(newNode);
    // 当前节点也有子节点，因此要把当前节点的children放到映射里
    if (!newNode.children) {
      newNode.children = [];
      idChildrenMap.set(obj.id, newNode.children);
    }
  });
  // 中间逻辑
  return out;
} 

3. 上面步骤中，完成了节点的遍历，以及在遍历过程中，会处理父子节点的 children 字段。但是我们定义的 out 还没有修改，这时候返回的还是个空数组。基于我们的假定， pid === 0 的部门是顶级，它应该是始终存在并且要放到 out 里的，加上判断即可：

function list2tree(arr) {
  const out = [];
  // 存储 id => children 的映射
  const idChildrenMap = new Map();
  arr.forEach((obj) => {
    // 下面处理把当前节点，放到父节点的 children 里
    let parentChildrenList = idChildrenMap.get(obj.pid);
    if (!parentChildrenList) {
      parentChildrenList = [];
      idChildrenMap.set(obj.pid, parentChildrenList);
    }
    // 新生成一个数据，不去修改 arr 里的数据
    const newNode = {
      id: obj.id,
      pid: obj.pid,
      name: obj.name,
      // 优先从映射缓存里，读取当前节点的子节点
      children: idChildrenMap.get(obj.id),
    };
    parentChildrenList.push(newNode);
    // 当前节点也有子节点，因此要把当前节点的children放到映射里
    if (!newNode.children) {
      newNode.children = [];
      idChildrenMap.set(obj.id, newNode.children);
    }
    // 判断当前节点是否为顶级，是的话就放到out里
    if (obj.pid === 0) {
      out.push(newNode);
    }
  });
  // 中间逻辑
  return out;
} 

题目点评

这个题目不算复杂，常规的遍历节点即可，需要注意的是，节点出现的顺序是未知的（子节点可能比父节点先遍历到），就需要在遍历过程中，使用额外的缓存（比如 Map） 来（提前）存储某个节点对应的子节点数组。

比较容易想到的是遍历2次，第1次先用 Map 收集节点id和节点数据，第2次再来处理子节点关系。

但是更理想的思路，是1次遍历处理完，在遍历过程中更新缓存。

另外，建议尽量保证函数是纯函数，执行过程不产生副作用（react同学笑了），不去修改传入的参数，遍历过程中生成新节点来返回。