代码人生|面试题——列表转树的深度解析与实战技巧

一、理解列表的本质

什么是列表？

列表本质上是一个数组，它作为一种容器，能够存储一系列元素。这些元素可以是任何类型的值，包括但不限于数字、字符串、对象等。数组的特点在于其连续性——每个元素都按顺序排列，并且可以通过下标直接访问。例如：


js
 代码解读
复制代码
const arr = [1, "2", { a: 1 }];

在这个例子中，arr[0] 是 1，arr[1] 是 "2"，而 arr[2] 是一个对象 { a: 1 }。这种灵活性使得列表成为了一种不可或缺的数据容器。

对于本题而言，我们的列表由若干个具有 id 和 title 属性的对象组成，同时每个对象还包含了一个 parentId 属性，用于标识其父节点。这样的设计为我们构建树形结构提供了坚实的基础。


js
 代码解读
复制代码
let list = [
    {
        id: '1',
        title: '节点1',
        parentId: '',
    },
    {
        id: '1-1',
        title: '节点1-1',
        parentId: '1'
    },
    {
        id: '1-2',
        title: '节点1-2',
        parentId: '1'
    },
    {
        id: '2',
        title: '节点2',
        parentId: ''
    },
    {
        id: '2-1',
        title: '节点2-1',
        parentId: '2'
    }
]

二、递归方法实现列表转树

要将一个平面列表转换为树形结构，我们可以采用递归的方法。递归是一种强大的工具，它通过将大问题分解为更小的问题来逐步解决复杂问题。在列表转树的情境下，递归的核心思想是：

大问题是啥？ 如何将一个平面的所有节点转变成树型结构？
小问题是啥？ 如何将 parentId 为某值的节点，转成树型结构？

具体来说，我们需要编写一个函数 listToTree，它接受两个参数：一个是待转换的列表 list，另一个是指定的 parentId。该函数会遍历整个列表，找出所有 parentId 匹配的节点，并将它们作为子节点添加到对应的父节点之下。


js
 代码解读
复制代码
function listToTree(list, parentId = "") {
  return list.filter(item => item.parent === parentId)
    .map(item => ({
      ...item,
      children: listToTree(list, item.id)
    }));
}
console.log(listToTree(list));

调用 listToTree(list) 即可开始转换过程，这里假设根节点的 parentId 为空字符串 ''。

为了得到更详细的信息，可以使用 JSON.stringify 方法格式化输出结果：


js
 代码解读
复制代码
console.log(JSON.stringify(list2Tree(list), null, 2));

得到如下图的详细信息，这不仅提高了输出的可读性，还便于调试和分析。

JSON.stringify 方法这是一个常用的 JavaScript 语句，用于将一个复杂的对象或数组以格式化的 JSON 字符串形式输出到控制台。它有三个参数：

value：要转换的对象或数组。
replacer（可选） ：一个函数或数组，用来选择或修改对象的属性值。如果是一个函数，则会调用该函数来处理每个键值对；如果是数组，则只包含这些键名的属性会被序列化；如果不提供此参数，则所有属性都会被序列化。
space（可选） ：用于控制缩进和空格的字符串或数字。如果是一个数字，则表示每一层级前添加的空格数；如果是一个字符串（最多 10 个字符），则直接使用该字符串进行缩进，这使得生成的 JSON 字符串更易读。

三、性能优化之道

时间复杂度 vs 空间换时间

虽然上述递归方法直观易懂，但它的效率并不高。每次递归调用都会重新遍历整个列表，导致时间复杂度达到 O(n²)。为了提高性能，我们可以利用哈希表来存储每个节点的信息，从而实现线性查找。


js
 代码解读
复制代码
function listToTree(list) {
    const map = {};   //空间换时间 json
    const root = [];
    // 初始化 map，将每个节点的 id 作为键，值为节点对象，并将 children 初始化为空数组
    list.forEach((item) => {
        //map 初始化， O(1)
        map[item.id] = { ...item, children: [] };
    })

    // 遍历列表，将每个节点添加到其父节点的 children 数组中
    list.forEach(item => {
        if (item.parentId) {
            // 如果节点有父节点，则将其添加到父节点的 children 数组中
            if (map[item.parentId]) {
                map[item.parentId].children.push(map[item.id]);
            }
        } else {
            // 如果节点没有父节点，则将其作为根节点
            root.push(map[item.id]);
        }
    });
    return root;
}

console.log(listToTree(list));
console.log(JSON.stringify(listToTree(list), null, 2));

在这里我们首先创建一个哈希表 Map 来存储每个节点的信息、root用于存储所有的根节点，然后用 forEach 方法遍历 list 数组中的每一个元素,对于每个节点，我们创建一个新的对象，复制了原对象的所有属性，并添加了一个空的 children 数组,然后将这个新对象存入 map 中，键为节点的 id。经过这一步，map 包含了所有节点的信息，并且每个节点都有一个空的 children 数组。

再次遍历列表，判断是否有父节点，有父节点的情况：使用 if (item.parentId) 检查当前节点是否有父节点（即 parentId 是否存在且不为 null 或 undefined）,再使用 if (map[item.parentId]) 确保父节点确实存在于 map 中，以避免访问不存在的键导致的错误，然后将当前节点添加到其父节点的 children 数组中；无父节点的情况：如果 parentId 是 null 或 undefined，说明这是一个根节点，将该节点直接推入 root 数组中，这就是我们构建好的树形结构。

四、结语

掌握列表转树的技巧，不仅是面试中的加分项，更是日常工作中不可或缺的能力。希望今天的分享能为大家提供一些启发，帮助大家更加熟练地处理复杂的数据结构！

一、理解列表的本质

二、递归方法实现列表转树

三、性能优化之道

四、结语

评论记录：