面试高频手撕题 | 25.实现一个列表转树形结构

一、知识点

1. 数据结构：了解树形结构的概念，包括节点、父节点、子节点和层次关系。
2. 递归：掌握递归的概念和使用方法，用于处理树形结构中的嵌套关系。
3. 遍历：熟悉列表的遍历方法，如使用 for 循环或递归遍历列表中的元素。

二、思路分析

1. 定义节点对象：为每个列表项创建一个节点对象，包含节点的值和子节点列表。
2. 构建树的根节点：根据列表的第一个元素创建根节点。
3. 递归处理列表的剩余部分：遍历列表的剩余部分，将每个元素作为子节点添加到当前节点的子节点列表中。
4. 处理节点之间的关系：根据列表中元素的顺序，确定父节点和子节点之间的关系。
5. 最终，你将得到一个树形结构，表示列表中元素的层次关系。

三、JavaScript 解答

以下是一个使用 JavaScript 实现列表转树形结构的代码示例：

// 定义一个节点类
class Node {
  constructor(value, children = []) {
    this.value = value;
    this.children = children;
  }
}

// 将列表转换为树形结构
function listToTree(data) {
  // 创建根节点
  const root = new Node(data[0]);

  // 递归处理剩余的列表项
  for (let i = 1; i < data.length; i++) {
    const item = new Node(data[i]);
    // 根据索引找到父节点
    const parent = findParentNode(root, i);
    if (parent) {
      parent.children.push(item);
    } else {
      root.children.push(item);
    }
  }

  return root;
}

// 找到指定索引对应的父节点
function findParentNode(node, index) {
  if (index === 0) {
    return null;
  }
  for (let i = 0; i < node.children.length; i++) {
    if (node.children[i].children.length > index) {
      return node.children[i];
    }
  }
  return null;
}

// 示例用法
const data = ["Root", "Node1", "Node2", "Node3", "Node4", "Node5"];
const tree = listToTree(data);
console.log(tree);

在这个示例中，我们首先定义了一个Node类来表示树形结构中的节点。每个节点包含一个值和一个子节点列表。

然后，我们定义了函数，它接受一个列表数据作为参数，并返回转换后的树形结构的根节点。在函数内部，我们首先创建根节点，并使用递归处理剩余的列表项。