阿里巴巴：将输入的数组组装成一颗树状的数据结构（一面）

[robinson90]

To：
robinson90

面试公司：
阿里

面试环节：
一面

问题：
将输入的数组组装成一颗树状的数据结构 要求程序具有侦测错误输入的能力，假如数据是下面的，

let dataArr =[
{id:1, name: 'i1'},
{id:2, name:'i2', parentId: 1},
{id:4, name:'i4', parentId: 3},
{id:3, name:'i3', parentId: 2},
{id:8, name:'i8', parentId: 7}
]

[robinson90]

梳理下我的解题思路：
返回的的为节点树，
那么首先需要一个根节点，
然后从根节点延伸出对应的children，
然后递归的去看子节点是否还有子节点。

那么针对上面的思路：
1 我们首先要理出那个节点是根节点，根节点特征很简单，没有父节点，设置该节点为根节点；
有父节点关联的均为一个子节点，那么根据其关联的父节点设置到一个对象父节点的数组中。
2 针对同一个父节点的子节点数组，因为关联的父节点是唯一的，与对象的键值对唯一匹配是一致的，我们不妨就按照父节点为键，然后把所有的子节点关联到一个键值对中。
3 根据根节点的id，不断的查看节点对象中以该节点id为键的children数组，赋值作为children属性；然后再查看其children中的每个节点的对象的id，再递归查找其children。也就是getChildren(node)这个方法。这里要考虑一个异常，就是不是每个节点的id都有子节点，当发现节点对象中没有时，其children是null，给与提示。

针对异常：
1 除了某些节点没有子节点的异常，在获取子节点的错误中已经处理
2 某些记录的节点，其父节点是不存在的。为了记录下这些节点，我们在每次遍历找到父节点的节点对象之后删除掉对应的属性。那么在继续遍历节点对象时，剩下的节点均为父节点不存在的元素。

 function getTreeData(arr) {
    if (!arr || !(arr instanceof Array)) return '错误的数据类型'
    if (!arr.length) return '空数组'
    var len = arr.length
    var rootObj = {id: null, name: null, children: []}
    var nodeObj = {}
    for (var i = 0;i < len; i++) {
      if (!arr[i].parentId) {
        rootObj = {
          id: arr[i].id,
          name: arr[i].name,
          children: [],
        }
      } else {
        if (nodeObj.hasOwnProperty(arr[i].parentId)) {
          nodeObj[arr[i].parentId].children.push(arr[i])
        } else {
          nodeObj[arr[i].parentId] = {}
          nodeObj[arr[i].parentId].children = []
          nodeObj[arr[i].parentId].children.push(arr[i])
        }
      }
    }
    // 整理根节点过程
    function getChildren(node) {
      if(nodeObj[node.id] && nodeObj[node.id].children){
          node.children = nodeObj[node.id].children
          delete(nodeObj[node.id])
          var len = node.children.length
          if (len > 0) {
              for (var i = 0; i < len; i++) {
                 getChildren(node.children[i])
              }
     }
      } else if(!nodeObj[node.id]){
        console.log(node.id + '没有children')
    }
  }
    getChildren(rootObj)
   for(var p in nodeObj){
     if(nodeObj.hasOwnProperty){
       console.warn(p + ':没有该父节点')
     }
   }
    return rootObj
  }

[LiuSandy]

利用浅拷贝原理

const buildTree = (data = [], config = {}) => {
  const id = (config && config.id) || 'id';
  const pid = (config && config.pid) || 'parentId';
  const children = (config && config.children) || 'children';

  // 把所有的ID映射为一个map 方便查询
  const idMap = {};
  // 找到父节点的放入 treeData
  const treeData = [];
  // 节点包含 pid 属性, 并且父节点不存在的放入 errorData
  const errorData = []

  data.forEach(v => {
    v && (idMap[v[id]] = v);
  });

  data.forEach(v => {
    if (v) {
      let parent = idMap[v[pid]];
      if (parent) {
        !parent[children] && (parent[children] = []);
        parent[children].push(v || []);
      } else if (!parent && v.hasOwnProperty(pid)) {
        errorData.push(v);
      } else {
        treeData.push(v);
      }
    }
  });
  // 树结构 错误数据同时返回
  // return {
  //   treeData,
  //   errorData
  // }
  // 只返回树结构
  return treeData
}

[alexwjj]

function toTree (data) {
// 删除 所有 children,以防止多次调用
data.forEach(function (item) {
delete item.children;
});

// 将数据存储为 以 id 为 KEY 的 map 索引数据列
var map = {};
data.forEach(function (item) {
map[item.id] = item;
});
// console.log(map, 'map');
var val = [];
data.forEach(function (item) {
// 以当前遍历项的pid,去map对象中找到索引的id
var parent = map[item.pid];
// 如果找到索引，那么说明此项不在顶级当中,那么需要把此项添加到，他对应的父级中
if (parent) {
(parent.children || (parent.children = [])).push(item);
} else {
// 如果没有在map中找到对应的索引ID,那么直接把 当前的item添加到 val结果集中，作为顶级
val.push(item);
}
});
return val;
}