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

一、知识点

树形结构和列表都是常见的数据结构，它们之间可以进行相互转换。树形结构是一种层次化的数据结构，每个节点可以有多个子节点，而列表是一种线性的数据结构，由一系列元素组成。

二、思路分析

1. 遍历树形结构：使用递归或迭代的方式遍历树形结构的每个节点。
2. 存储节点信息：在遍历过程中，将节点的信息存储到一个列表中，可以按照需要的顺序进行存储。
3. 处理节点关系：根据树形结构的特点，处理节点之间的父子关系，在列表中表示出来。

三、JavaScript 解答

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

// 定义树形结构节点的数据结构
class Node {
  constructor(value, children = []) {
    this.value = value;
    this.children = children;
  }
}

// 示例树形结构
const tree = new Node("Root", [
  new Node("Node1", [
    new Node("Node1-1"),
    new Node("Node1-2"),
  ]),
  new Node("Node2", [
    new Node("Node2-1"),
    new Node("Node2-2"),
    new Node("Node2-3"),
  ]),
]);

// 定义将树形结构转换为列表的函数
function treeToList(node) {
  // 创建用于存储列表的数组
  const result = [];

  function dfs(node) {
    // 将当前节点的值添加到列表中
    result.push(node.value);

    // 递归遍历子节点
    for (const child of node.children) {
      dfs(child);
    }
  }

  dfs(node);
  return result;
}

// 打印转换后的列表
console.log(treeToList(tree));

在上述示例中，首先定义了一个树形结构节点的类Node，每个节点包含一个值和一个子节点数组。然后，创建了一个示例的树形结构tree。接下来，定义了treeToList函数，它使用递归函数dfs来遍历整个树形结构，将节点值依次添加到结果列表中，并通过递归处理子节点。最后，调用treeToList函数并打印输出结果。

四、Java 解答

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

// 定义节点类
class Node {
    String value;
    List<Node> children;

    public Node(String value, List<Node> children) {
        this.value = value;
        this.children = children;
    }
}

public class TreeToListConverter {
    public static void main(String[] args) {
        // 创建一个示例的树形结构
        Node root = new Node("Root", Arrays.asList(
                new Node("Node1", Arrays.asList(
                        new Node("Node1-1"),
                        new Node("Node1-2")
                )),
                new Node("Node2", Arrays.asList(
                        new Node("Node2-1"),
                        new Node("Node2-2"),
                        new Node("Node2-3")
                ))
        ));

        // 调用 treeToList 函数将树形结构转换为列表
        List<String> list = treeToList(root);

        // 打印转换后的列表
        System.out.println(list);
    }

    public static List<String> treeToList(Node node) {
        List<String> result = new ArrayList<>();

        // 将当前节点的值添加到列表中
        result.add(node.value);

        // 递归遍历子节点
        for (Node child : node.children) {
            result.addAll(treeToList(child));
        }

        return result;
    }
}

在上述示例中，首先定义了一个Node类来表示树形结构中的节点，每个节点包含一个值和一个子节点列表。然后，在TreeToListConverter类的main方法中创建了一个示例的树形结构，并调用treeToList函数将其转换为列表。treeToList函数使用递归的方式遍历整个树形结构，将节点值依次添加到结果列表中，并通过递归处理子节点。最后，返回转换后的列表并进行打印输出。

五、总结

通过以上示例，我们可以使用递归或迭代的方式遍历树形结构，并将节点信息存储到列表中，从而实现树形结构到列表的转换。具体的实现方式可以根据实际需求进行选择。