Trie迭代器，后缀排序

Question

我需要实现一个trie的迭代器。比方说，我有

a 
    /\ 
    b c 
    /\ 
d e 

如果当前iterator.state =“ABD”，我想有iterator.next.state =“安倍”，那么“交流”。在每个级别，节点按字典顺序排序（例如，在级别2上，c在b之后）。这也应该发生在log（n）时间，其中n是节点的数量。

我能想到的一个解决方案是：考虑一个特殊情况，每个分支具有相同的高度。我认为一个相当酷的实现是为每个“级别”维护一棵平衡的树。在询问：“在abd之后跟随什么字符串”时，可以在与第三级关联的树中搜索大于“b”的第一个元素，给出“abe”。

但是，由于必须创建树木，这可能不切实际。

Answer 1

如果我正确理解问题，则迭代器状态可能是当前字符串和指向当前位置的指针。然后，移动到下一个元素：

1. 如果您当前的位置有一个兄弟，将它和当前字符串与当前位置的字符替换最后一个字符。

2. 否则，删除最后一个字符并上去树。如果你试图从根开始，那么你就完成了。否则，转到步骤1

因此，例如，当你在ABD（在你的例子），当前字符串是“ABD”和指针指向“d”。要移动到下一个元素，将字符串更改为“ab”，移动到兄弟节点（'e'）并将其添加到字符串中，产生“abe”。之后，你会上升，因为没有兄弟姐妹，然后到b的兄弟姐妹，产生正确的下一个值'ac'。

正如你所看到的，最坏的情况下，这些步骤中的每一步都需要一直回到根，才能找到兄弟姐妹;那是你要求的日志。