一道扁平数据转树结构面试题

一、前言

扁平数据转树状结构，是前端工程师必备的功能之一，这篇文章记录一道相关的面试题

二、相关知识点

扁平数据转树状结构的要点有两个：

确定父子关系

如何确认数据之间的父子关系是功能的重点，找到确认方法就可以事半功倍

浅拷贝

在转换的过程中，我们会用到浅拷贝的知识

三、题目和解法

const arr = [
  { id: '1.1', label: '武汉市' },
  { id: '1.1.2', label: '武汉市洪山区' },
  { id: '1.3.1', label: '孝感市孝南区' },
  { id: '1.5.1', label: '黄石市黄石港区' },
  { id: '1.2', label: '宜昌市' },
  { id: '1', label: '湖北省' },
  { id: '1.1.1', label: '武汉市江夏区' },
  { id: '1.2.1', label: '宜昌市伍家岗区' },
  { id: '1.3', label: '孝感市' }
]

/**
 *
 * @param {Array} originArr
 */
const arrayToTree = (originArr) => {
  const result = []; // 存储要返回的数据
  const resultIdsSet = new Set(); // 存储命中的ID

  originArr.forEach(item => {
    if (item.id.length === 1) {
      result.push(item)
    }
    item.children = originArr.filter(originItem => {
      // 将ID根据.分割成数组
      const originItemIdArr = originItem.id.split('.');
      const itemIdArr = item.id.split('.');

      /**
       *  父子关系说明：1 父ID的位数只比子ID少一位
          2 匹配的时候，父ID的位数上的每个值可以和子ID位数上的值匹配上即可确定关系
       */
      if (itemIdArr.length + 1 === originItemIdArr.length && itemIdArr.every((i, k) => i === originItemIdArr[k])) {
        resultIdsSet.add(item.id);
        resultIdsSet.add(originItem.id);
        return tree;
      }
      return false;
    })
  })
  // 最后需要找出未命中的ID放在数组后面返回
  return [...result, ...arr.filter(item => !resultIdsSet.has(item.id))];
}

console.log(arrayToTree(arr))