面试高频手撕题 | 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类来表示树形结构中的节点。每个节点包含一个值和一个子节点列表。

然后，我们定义了listToTree函数，它接受一个列表数据作为参数，并返回转换后的树形结构的根节点。在函数内部，我们首先创建根节点，并使用递归处理剩余的列表项。对于每个列表项，我们创建一个新的节点，并根据其在原始列表中的索引找到父节点，将其添加为子节点。

最后，我们通过调用listToTree函数并传递示例数据来创建一个树形结构，并将其打印到控制台上。

四、Java 解答

在 Java 中，你可以使用递归的方式来实现将列表转换为树形结构。以下是一个简单的示例代码：

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    String value;
    List<TreeNode> children;

    public TreeNode(String value) {
        this.value = value;
        this.children = new ArrayList<>();
    }
}

public class ListToTreeConverter {
    public static TreeNode convert(List<String> data) {
        // 创建根节点
        TreeNode root = new TreeNode(data.get(0));

        for (int i = 1; i < data.size(); i++) {
            String item = data.get(i);
            // 根据索引找到父节点
            TreeNode parent = findParentNode(root, i);
            if (parent == null) {
                root.children.add(new TreeNode(item));
            } else {
                parent.children.add(new TreeNode(item));
            }
        }

        return root;
    }

    private static TreeNode findParentNode(TreeNode node, int index) {
        if (index == 0) {
            return null;
        }
        for (int i = 0; i < node.children.size(); i++) {
            if (node.children.get(i).children.size() > index) {
                return node.children.get(i);
            }
        }
        return null;
    }
}

public class Main {
    public static void main(String[] args) {
        List<String> data = new ArrayList<>();
        data.add("Root");
        data.add("Node1");
        data.add("Node2");
        data.add("Node3");
        data.add("Node4");
        data.add("Node5");

        TreeNode tree = ListToTreeConverter.convert(data);
        System.out.println(tree);
    }
}

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

然后，我们定义了convert方法，它接受一个列表数据作为参数，并返回转换后的树形结构的根节点。在方法内部，我们首先创建根节点，并使用递归处理剩余的列表项。对于每个列表项，我们找到其在父节点中的位置，并将其添加为子节点。

最后，在Main类的main方法中，我们创建一个示例列表，并调用convert方法将其转换为树形结构。然后，我们打印转换后的树形结构。

希望这个示例对你有帮助。

五、总结

通过以上示例，我们可以使用递归或迭代的方式将列表转换为树形结构。具体的实现方式可以根据实际需求进行选择。