从边列表（节点对）构建二叉树

Question

我想从一个非常不寻常的输入构建一个二叉树。输入包含：

1. 节点总数。

2. 根的整数标签。

3. 所有边（相互连接的顶点/节点）的列表。列表中的边是未排序的，只有一个规则用于确定左/右子元素 - 列表中第一个出现的边中的子元素始终位于左侧。顶点对中子/父的顺序也是随机的。

我提出了一些简单的解决方案，但它们需要对所有边的列表进行多次搜索（我基本上会找到其中有标记根的 2 条边，并对所有子树重复此过程。）

我想这种简单的方法对于具有大量节点的树来说效率非常低，但我想不出其他的办法。

有什么更有效的算法来解决这个问题的想法吗？

这是一个更好的可视化示例：

输入：5 个节点，根标记为 2，边列表：[(1,0),(1,2),(2,3),(1,4)]

这棵树看起来像这样：

        2
    1       3
 0     4

Answer 1

澄清给定的边列表是否被声明为有向的很重要。

如果边以有向方式给出（即规定任何给定边AB还包括A是B的父代的信息），则将边存储在邻接列表中，同时记录数组中每个顶点的传入边的数量应该足够了。一旦你遍历了传入边的数组，具有 0 个传入边的顶点（即父节点）应该是根。然后，您可以以线性时间复杂度运行DFS来遍历该图，并将其放入最适合您需求的任何数据结构中。

如果给定的边被声明为无向，则方案会发生一些变化。在这种情况下，您就没有传入和传出边缘的概念。在这种情况下，由于没有指定数组的结构（例如BST等），您基本上可以将任何少于 3 个边的节点视为根，并如上所述运行 DFS。（具有单个子节点的所有叶子节点和中间节点）