algorithm - 使用迭代器和堆栈的二进制搜索树按顺序遍历 - 空间复杂度 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)”。我问他怎么做，他说“我们只需要存储 parent ”。(我可能听错了。他的口音很重。)我的实现是存储每个离开 child 的节点. 我只是想当然地接受了他的回答。

但是，经过采访，我认为，即使我们只需要存储父节点(而不是叶节点)，它仍然是O(N)。它是精确的 O(N/2)，但仍然是 O(N)。我相信任何有 child 的节点都应该存储在堆栈中。如何不呢？

唯一可以达到 O(logN) 空间的情况是当二叉树只有一个分支不断向下时(而不是具有完整叶子的平衡树。)

我在这里错过了什么？如果有人能解释如何使用迭代器将空间复杂度进一步降低到 O(log N)，我将不胜感激!

Answer 1

我想我理解你的困惑。

考虑这棵树(这样我们就有了一个具体的例子可以引用):

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

在遍历这棵树的过程中，您需要存储每个有左子节点的节点——三个节点 A、B 和 C。通常，对于任何树，您都需要在迭代过程中存储多达 O(n) 个节点。这似乎就是你说 O(n) 的原因。

但是您不需要一次保留所有这些节点。一旦迭代到 E，您就不再需要为任何事情保留节点 B。在迭代中的任何给定点，您只需要保留 current 节点的 later 祖先——它最多有两个节点，即 A 和 B(当您的当前节点是 D 时)。通常，对于任何树，您永远不需要同时存储超过 O(h) 个节点，其中 h 是树的高度。假设一棵平衡树(正如您的面试官所清楚的那样)，这意味着 O(log n)。

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