我想合并两个Trie结构，但是我能想到的最好的复杂性是
获取其他trie的值列表：o（n），n是trie中的节点的数量。从列表介绍目标trie插入所有值：n * o（m），m是密钥的长度考虑到最坏的情况，关键是n尺寸的，不是合并O（n^2）的复杂性吗？
有什么更好的方法吗？
复杂性将为o（n m）。您需要两个迭代器（树节点指针）都从相应树的根节点开始。
您看孩子，如果一个孩子仅存在于一个迭代器中，则只需将孩子复制到结果中（如果您可以直接移动孩子（分配指针）甚至更好）。如果双方都出现了一个孩子，则在各自的孩子上递归地致电该功能。
这样，您只花时间合并模棱两可的节点，您可以一次复制/移动整个子树。
如果您运行了原始想法，则复杂性将为o（n*m），其中n是条目的数量，m是条目的平均长度。您不会得到O（n^2），因为如果所有节点都用于单个条目（您的最坏情况），您仍然只需要复制一次。