algorithm - 合并两个二叉树

Question

我想合并两个特里结构，但我能想到的最好的复杂性是

从其他 trie 获取值列表：O(n)，n 是 trie 中的节点数。从list intro target trie中插入所有值：n * O(m)，m是key的长度考虑到，最坏的情况下，key的大小是n，合并的复杂度不是O(n^2)吗？

有没有更好的方法呢？

Answer 1

复杂度将是 O(N+M)。您需要两个迭代器（树节点指针）都从各自树的根节点开始。

如果孩子只存在于其中一个迭代器中，则查看孩子，然后您只需将该孩子复制到结果中（如果您可以直接移动孩子（分配指针）更好）。如果双方都存在孩子，则在各自的孩子上递归调用该函数。

这样，您只需花时间合并不明确的节点，就可以一次性复制/移动整个子树。

如果你运行你最初的想法，复杂性将是 O(N*M)，其中 N 是条目数，m 是条目的平均长度。您不会得到 O(N^2) ，因为如果所有节点都用于单个条目（最坏的情况），您仍然只需要复制该条目一次。