algorithm - 如何构建仅知道连接哪些节点的二叉树？

Question

我必须构建一棵二叉树，但我不知道哪个节点是父节点、左节点或右节点。我只知道连接了哪些节点。示例:对于这样的输入:

6 4
5 7
9 7
1 5
10 4
3 4
2 6
7 8
5 6

(从 1 开始，总有一条路)树应该是这样的:

其中一个输入我还给出了节点数。有什么想法、提示吗？

Answer 1

从边列表中，可以很容易地创建一棵树。

你可以找到哪些是叶子节点，只需要搜索哪些节点只出现在一条边上。但是，不可能知道哪个叶节点是树的头部。在树结构中，可以选择任何叶子，将其选为头部，并对树重新排序，这将是一棵有效的树。

还有树同构的问题，可以交换左右子树得到一棵有效的树。

总而言之，从这个列表中你可以得到 6 个正面，并且在每 4 个可能的交换中，所以总共有 24 个不同的有效树。