java - 如何从路径编码重建二叉树？

Question

假设我有以下形式的输入:

(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

其中第二个字段表示从根节点开始的路径，空字段表示根节点，()表示数据结束。

输出将是levelorder:5 4 8 11 13 4 7 2 1

如何重建二叉树？请注意，有可能存在节点丢失的可能性。例如，存在 LLL 和 L，但没有节点连接它们，对于这种情况，应该创建一个值为 -1 的节点来连接它们。

到目前为止我发现的是创建一个 NodePath 类来存储数据和路径，例如NodePath(11,LL) 都是字符串值。接下来，我遍历每个字符串标记。在迭代过程中，我比较路径长度并将它们存储在 LinkedList 中。例如。 11,LL --> 7,LLL 当 8 出现时变成 8,R --> 11,LL --> 7,LLL

现在，这就是我被困的地方，因为我不知道如何区分 LLL 和 LLR 以及如何相应地构建二叉树。恐怕我会将 LLL 和 LLR 放在相反的位置。

Answer 1

您可以使用键值对构建一个 Map - 键是您的路径(“LLL”)，值是数字(“7”)。

第二步遍历 Map 的 EntrySet 并自上而下构建每条路径，在没有节点的地方创建默认值为“-1”的新节点，并尽可能使用现有节点.