我有一个关于二叉排序树设计原则的问题。
我需要创建一个二叉表达式树的深度副本，我通过遍历树中的所有节点并创建一个新的，相同的节点来实现这一点。
我已经为其他用途设置了一个treeIterator，并且想知道迭代器是否会更快，更慢，或者与递归执行相同的速度/内存使用。
谢谢!
我认为递归会更快。
我不知道你的迭代器的具体实现，但我假设它会到达每个节点。如果您的BST基于根节点结构，那么遍历每个节点(就像在迭代器中一样)将比递归慢。
我将如何实现它:
递归,创建一个新的根节点(与原始根节点相同)。添加原始根的左节点和右节点的副本。(如果存在)
有两个部分:(1)遍历树和(2)创建一个新的树副本。我假设你所说的迭代是指手动维护树中位置的循环。这可能比递归更快/更少内存。但是，在构建新树时，最好使用递归，并在遍历过程中构建树。如果你迭代并将节点插入到一棵新树中，这将花费O(nlgn)，另一方面，递归只需要O(n)，尽管你可能会在很深的树中耗尽你的堆栈。
您没有指定如何实现迭代器。迭代器只是一个接口，而不是特定的实现。
在BST中搜索需要O(log n)时间，这意味着在任何时间点，找到下一个节点需要O(log n)时间。
解释:下一个节点总是右子树中最小的元素，或者是当前节点的父节点。在任何情况下，它都不会超过log n时间。
除非你的迭代器实现所需的时间少于O(log n)，否则递归会更快。
编辑:我需要指出，这里的0符号是平均情况，而不是最坏的情况。然而，假设你有一个相当平衡的树，log n仍然适用。