题目描述

根据 id 和 parent_id 的对应关系，将一个数组转成树状结构。

示例：

[
  { "id": 12, "parent_id": 1, "name": "朝阳区" },
  { "id": 241, "parent_id": 24, "name": "田林街道" },
  { "id": 31, "parent_id": 3, "name": "广州市" },
  { "id": 13, "parent_id": 1, "name": "昌平区" },
  { "id": 2421, "parent_id": 242, "name": "上海科技绿洲" },
  { "id": 21, "parent_id": 2, "name": "静安区" },
  { "id": 242, "parent_id": 24, "name": "漕河泾街道" },
  { "id": 22, "parent_id": 2, "name": "黄浦区" },
  { "id": 11, "parent_id": 1, "name": "顺义区" },
  { "id": 2, "parent_id": 0, "name": "上海市" },
  { "id": 24, "parent_id": 2, "name": "徐汇区" },
  { "id": 1, "parent_id": 0, "name": "北京市" },
  { "id": 2422, "parent_id": 242, "name": "漕河泾开发区" },
  { "id": 32, "parent_id": 3, "name": "深圳市" },
  { "id": 33, "parent_id": 3, "name": "东莞市" },
  { "id": 3, "parent_id": 0, "name": "广东省" }
]

转换为：

[{
	"id": 2,
	"parent_id": 0,
	"name": "上海市",
	"children": [{
		"id": 21,
		"parent_id": 2,
		"name": "静安区",
		"children": []
	}, {
		"id": 22,
		"parent_id": 2,
		"name": "黄浦区",
		"children": []
	}, {
		"id": 24,
		"parent_id": 2,
		"name": "徐汇区",
		"children": [{
			"id": 241,
			"parent_id": 24,
			"name": "田林街道",
			"children": []
		}, {
			"id": 242,
			"parent_id": 24,
			"name": "漕河泾街道",
			"children": [{
				"id": 2421,
				"parent_id": 242,
				"name": "上海科技绿洲",
				"children": []
			}, {
				"id": 2422,
				"parent_id": 242,
				"name": "漕河泾开发区",
				"children": []
			}]
		}]
	}]
}, {
	"id": 1,
	"parent_id": 0,
	"name": "北京市",
	"children": [{
		"id": 12,
		"parent_id": 1,
		"name": "朝阳区",
		"children": []
	}, {
		"id": 13,
		"parent_id": 1,
		"name": "昌平区",
		"children": []
	}, {
		"id": 11,
		"parent_id": 1,
		"name": "顺义区",
		"children": []
	}]
}, {
	"id": 3,
	"parent_id": 0,
	"name": "广东省",
	"children": [{
		"id": 31,
		"parent_id": 3,
		"name": "广州市",
		"children": []
	}, {
		"id": 32,
		"parent_id": 3,
		"name": "深圳市",
		"children": []
	}, {
		"id": 33,
		"parent_id": 3,
		"name": "东莞市",
		"children": []
	}]
}]

思路解析

1. 基于 hash + 数组遍历： 先将数组转成一个对象，以 id 作为key，然后遍历数组，查找 parent_id对应的对象，往里面添加数据即可；

2. 类似 BFS 的思路，先遍历根节点，然后通过根节点的 id 查找其对应的子节点，依次递归查询

代码实现

1. 基于 hash + 数组遍历方式

function arrayToTree(list, rootId = 0) {
  const nodeMap = {};
  for (let item of list) {
    nodeMap[item.id] = item;
  }

  const result = [];
  for (let item of list) {
    const pId = item.parent_id;
    if (pId === rootId) {
      result.push(item);
    } else {
      const target = nodeMap[pId];
      target.children = target.children || [];
      target.children.push(item);
    }
  }
  return result;
}

2. 递归思路

function arrayToTree(list, rootId = 0) {
  return list.filter(item => item.parent_id === root).map(item => ({
    ...item,
    children: arrayToTree(list, item.id)
  }))
}

测试用例

console.log(JSON.stringify(arrayToTree([
  { "id": 12, "parent_id": 1, "name": "朝阳区" },
  { "id": 241, "parent_id": 24, "name": "田林街道" },
  { "id": 31, "parent_id": 3, "name": "广州市" },
  { "id": 13, "parent_id": 1, "name": "昌平区" },
  { "id": 2421, "parent_id": 242, "name": "上海科技绿洲" },
  { "id": 21, "parent_id": 2, "name": "静安区" },
  { "id": 242, "parent_id": 24, "name": "漕河泾街道" },
  { "id": 22, "parent_id": 2, "name": "黄浦区" },
  { "id": 11, "parent_id": 1, "name": "顺义区" },
  { "id": 2, "parent_id": 0, "name": "上海市" },
  { "id": 24, "parent_id": 2, "name": "徐汇区" },
  { "id": 1, "parent_id": 0, "name": "北京市" },
  { "id": 2422, "parent_id": 242, "name": "漕河泾开发区" },
  { "id": 32, "parent_id": 3, "name": "深圳市" },
  { "id": 33, "parent_id": 3, "name": "东莞市" },
  { "id": 3, "parent_id": 0, "name": "广东省" }
]), null, 2))