需求背景
在需要存储树结构的情况下，一般由于使用的关系型数据库（如 MySQL），是以类似表格的扁平化方式存储数据。因此不会直接将树结构存储在数据库中
image.png
代表了如下的树状结构：
{
id: 1,
pid: 0,
data: 'a',
children: [
{id: 2, pid: 1, data: 'b'},
{id: 3, pid: 1, data: 'c'},
]
}
🌰
const list = [
{ pid: null, id: 1, data: "1" },
{ pid: 1, id: 2, data: "2-1" },
{ pid: 1, id: 3, data: "2-2" },
{ pid: 2, id: 4, data: "3-1" },
{ pid: 3, id: 5, data: "3-2" },
{ pid: 4, id: 6, data: "4-1" },
];
方法一
递归解法：该方法简单易懂，从根节点出发，每一轮迭代找到 pid 为当前节点 id 的节点，作为当前节点的 children，递归进行。
function listToTree(
list,
pid = null,
{ idName = "id", pidName = "pid", childName = "children" } = {}
) {
return list.reduce((root, item) => {
// 遍历每一项，如果该项与当前 pid 匹配，则递归构建该项的子树
if (item[pidName] === pid) {
const children = listToTree(list, item[idName]);
if (children.length) {
item[childName] = children;
}
return [...root, item];
}
return root;
}, []);
}
//时间复杂度为 O(n^2)
方法二
迭代法：利用对象在 js 中是引用类型的原理。第一轮遍历将所有的项，将项的 id 与项自身在字典中建立映射，为后面的立即访问做好准备。 由于操作的每一项都是对象，结果集 root 中的每一项和字典中相同 id 对应的项实际上指向的是同一块数据。后续的遍历中，直接对字典进行操作，操作同时会反应到 root 中。
function listToTree(
list,
rootId = null,
{ idName = "id", pidName = "pid", childName = "children" } = {}
) {
const record = {}; // 用空间换时间，用于将所有项的 id 及自身记录到字典中
const root = [];
list.forEach((item) => {
record[item[idName]] = item; // 记录 id 与项的映射
item[childName] = [];
});
list.forEach((item) => {
if (item[pidName] === rootId) {
root.push(item);
} else {
// 由于持有的是引用，record 中相关元素的修改，会在反映在 root 中。
record[item[pidName]][childName].push(item);
}
});
return root;
}
//时间复杂度为 O(n)
方法二变体一
在解法二的基础上，将两轮迭代合并成一轮迭代。采用边迭代边构建的方式：
function listToTree(
list,
rootId = null,
{ idName = "id", pidName = "pid", childName = "children" } = {}
) {
const record = {}; // 用空间换时间，用于将所有项的 id 及自身记录到字典中
const root = [];
list.forEach((item) => {
const id = item[idName];
const parentId = item[pidName];
// 如果该项不在 record 中，则放入 record。如果该项已存在 （可能由别的项构建 pid 加入），则合并该项和已存在的数据
record[id] = !record[id] ? item : { ...item, ...record[id] };
const treeItem = record[id];
if (parentId === rootId) {
// 如果是根元素，则加入结果集
root.push(treeItem);
} else {
// 如果父元素不存在，则初始化父元素
if (!record[parentId]) {
record[parentId] = {};
}
// 如果父元素没有 children, 则初始化
if (!record[parentId][childName]) {
record[parentId][childName] = [];
}
record[parentId][childName].push(treeItem);
}
});
return root;
}
//时间复杂度为 O(n)
方法二变体二
record 字典仅记录 id 与 children 的映射关系，代码更精简：
function listToTree(
list,
rootId = null,
{ idName = "id", pidName = "pid", childName = "children" } = {}
) {
const record = {}; // 用空间换时间，仅用于记录 children
const root = [];
list.forEach((item) => {
const newItem = Object.assign({}, item); // 如有需要，可以复制 item ，可以不影响 list 中原有的元素。
const id = newItem[idName];
const parentId = newItem[pidName];
// 如果当前 id 的 children 已存在，则加入 children 字段中，否则，初始化 children
// item 与 record[id] 引用同一份 children，后续迭代中更新 record[parendId] 就会反映到 item 中
newItem[childName] = record[id] ? record[id] : (record[id] = []);
if (parentId === rootId) {
root.push(newItem);
} else {
if (!record[parentId]) {
record[parentId] = [];
}
record[parentId].push(newItem);
}
});
return root;
}
//时间复杂度为 O(n)
总结
● 递归法：在数据量增大的时候，性能会急剧下降。好处是可以在构建树的过程中，给节点添加层级信息。
● 迭代法：速度快。但如果想要不影响源数据，需要在 record 中存储一份复制的数据，且无法在构建的过程中得知节点的层级信息，需要构建完后再次深度优先遍历获取。
● 迭代法变体一：按需创建 children，可以避免空的 children 列表。
时间复杂度
代码的执行时间 T(n)与每行代码的执行次数 n 成正比，人们把这个规律总结成这么一个公式：T(n) = O(f(n))；
大O时间复杂度并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。
● 只关注循环执行次数最多的一段代码
function total(n) { // 1
var sum = 0; // 2
for (var i = 0; i < n; i++) { // 3
sum += i; // 4
} //5
} //6
//只有第 3 行和第 4 行是执行次数最多的，分别执行了 n 次，那么忽略常数项，所以此段代码的时间复杂度就是 O(n)。
● 加法法则：总复杂度等于量级最大的那段代码的复杂度。
function total(n) {
// 第一个 for 循环
var sum1 = 0;
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
sum1 = sum1 + i + j;
}
}
// 第二个 for 循环
var sum2 = 0;
for(var i=0;i<1000;i++) {
sum2 = sum2 + i;
}
// 第三个 for 循环
var sum3 = 0;
for (var i = 0; i < n; i++) {
sum3 = sum3 + i;
}
}
//取最大量级，所以整段代码的时间复杂度为 O(n2)。
● 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
function f(i) {
var sum = 0;
for (var j = 0; j < i; j++) {
sum += i;
}
return sum;
}
function total(n) {
var res = 0;
for (var i = 0; i < n; i++) {
res = res + f(i); // 调用 f 函数
}
}
// O(n2)。
function total1(n) {
var sum = 0;
var i = 1;
while (i <= n) {
sum += i;
i = i * 2;
}
}
function total2(n) {
var sum = 0;
for (var i = 1; i <= n; i = i * 2) {
sum += i;
}
}
//2x = n => x = log2n => O(logn)
🌰
function total(n) {
var sum = 0;
for (var i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
function total(n) {
var sum = n * (n + 1) / 2
return sum;
}
注：来源于小哥的分享
