使用迭代器和栈实现二叉搜索树的中序遍历 - 空间复杂度 O(log N)？如何实现？

Question

在电话面试中，我被要求使用迭代器和栈（非递归）实现二叉搜索树的中序遍历。我不允许使用父指针。以下是给出的起始代码。

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}};

class BTIterator
{
public:
    BTIterator(TreeNode *root){


    };
    TreeNode* next() {

    }
    bool hasNext() {

    }

};

测试函数：

void TestFunc(TreeNode *root) {
BTIterator bti(root);
while(bti->hasNext()) {
  cout << bti->next()->val << " ";
}}

我被要求在上述代码中实现BTIterator、next和hasNext。于是我就这样做了。随后的问题是时间复杂度和空间复杂度是什么。我回答说时间复杂度为O(N)，空间复杂度为O(N)。然而，面试官说：“你可以将空间复杂度进一步降低到O(log N)。”我问他怎么做，他说：“我们只需要存储父节点。”（可能我听错了，他的口音很重。）我的实现是存储每个有左孩子的节点。我只是简单地接受了他的答案。

然而，在面试之后，我认为即使我们只需要存储父节点（而不是叶节点），它仍然是O(N)。确切地说，是O(N/2)，但仍然是O(N)。我认为任何有左孩子的节点都应该存储在栈中。如何不存储？

唯一能实现空间复杂度为O(logN)的情况是二叉树只有一个分支一直向下延伸（不是具有完整叶子的平衡树）。

我在这里缺少什么？如果有人能解释如何使用此迭代器降低空间复杂度至O(logN)，我将不胜感激！

- aerin

---

你必须实际努力才能使其不同于O(logN)空间 - 在BTIterator中拥有堆栈对象的明显方法是O(logN)，因为logN是任何时刻所需的最大堆栈深度。你成功做到了什么不是O(logN)的事情？ - Chris Dodd

@ChrisDodd 空间复杂度会是 O(n)，以保存 n 个节点？！！ - vish4071

@vish4071：你只需要在栈中存储最大的树深度--平均情况下为O(logn)，但是如下面的答案所述，如果你有一个不平衡的二叉树，基本上就是一个列表，最坏情况下为O(n)。 - Chris Dodd

哦...从 @ChrisDodd 那里学到了新东西。谢谢。 - vish4071

Answer 1

我想我了解你的困惑。

考虑以下树形结构（只是为了我们有一个具体的例子进行参考）：

         A
       /   \
      B     C
     / \   / \
    D   E F   G

在遍历该树的过程中，您需要存储每个具有左子节点的节点——即 A、B 和 C 三个节点。通常情况下，对于任何一棵树，您需要在迭代过程中最多存储 O(n) 个节点。这似乎就是为什么您会说 O(n) 的原因。

但是，您不需要同时保留所有这些节点。一旦向前迭代到 E，您就不再需要保存节点 B。在迭代的任何时刻，您只需要保留当前节点的后代节点——最多只有两个节点，即 A 和 B（当您的当前节点是 D 时）。通常情况下，对于任何一棵树，您永远不需要同时存储超过 O(h) 个节点，其中 h 是树的高度。假设树是平衡的（正如您的面试官明确表示的那样），那么这意味着 O(log n)。

因此，您不需要额外的 O(n) 空间，因为您可以随时间重复使用空间。 这就是使用堆栈的重点：您可以从顶部弹出一个元素，然后将新元素推入其位置。

- ruakh

---

啊...一下子！就是这个关键词。感谢你的回答。 - aerin

Answer 2

如果二叉搜索树（BST）不平衡且必须使用堆栈方法，则空间复杂度为O(h)，其中h是给定BST的高度。显然，如果要遵循堆栈方法，则无法实现更好的空间复杂度。

如果给定的BST是平衡的或者允许您平衡它，则可以实现O(logn)的空间复杂度，其中n是给定BST中节点的数量。

显然，如果你不强制使用堆栈方法，你可以在时间和空间复杂度的权衡中玩耍。如果允许预处理，则使用Morris in-order traversal using threading进行O(n)额外空间和O(1)时间复杂度。或者，如果不允许预处理，你可以只存储current TreeNode。当调用next()时，在平衡BST中以O(logn)时间和非平衡BST中以O(n)时间找到存储的当前TreeNode的最小上界。在从next()返回之前更新current。因此，你可以用时间换取O(1)空间复杂度。

- Shridhar R Kulkarni