使用迭代器和堆栈的二叉搜索树 in-order 遍历 - SPACE 复杂度 O(log N)？如何？

Question

在 phone 面试期间，我被要求使用迭代器和堆栈（非递归）实现二叉搜索树 in-order 遍历。我不被允许使用 parent 指针。

这是给我的起始代码。

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。

所以我做到了。后续问题是时间和 space 复杂度是多少。所以我回答时间是O(N)，space是O(N)。然而，面试官说“你可以进一步降低 space 的复杂性 O(log N)”。我问他怎么做，他说 "we only need to store the parents"。（我可能听错了。他的口音很重。）我的实现是存储每个离开 children 的节点.我只是把他的回答当成理所当然了

但是，经过采访，我觉得，即使我们只需要存储parents（不是叶子节点），它仍然是O(N)。它是 precisley O(N/2) 但这仍然是 O(N)。我相信 任何离开 children 的节点都应该存储在堆栈中。怎么不呢？

唯一可以实现 space O(logN) 的情况是当二叉树只有一个分支不断向下时（不是具有完整叶子的平衡树。）

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

Answer 1

如果二叉搜索树（BST）是不平衡的，我们必须使用堆栈方法，那么 O(h) 是 space 的复杂度，其中 h 是给定的高度BST。显然，如果要遵循堆栈方法，不可能获得更好的space复杂度。

如果给定的 BST 是平衡的，或者如果你允许平衡它，那么有可能实现 O(logn) space 复杂度，其中 n 是节点的数量给出 BST.

显然，如果您不被迫使用堆栈方法，则可以权衡时间和 space 复杂性。如果允许预处理，则使用 Morris in-order traversal using threading 以获得 O(n) 额外的 space 和 O(1) 时间复杂度。或者，如果不允许预处理，您可以只存储 current TreeNode。当调用next()时，平衡BST在O(logn)时间，非平衡BST在O(n)时间找到存储的当前TreeNode的最小上界。从 next() 更新 return 之前的 current。因此，您可以用时间换取 O(1) space 复杂性。

Answer 2

我想我理解你的困惑。

考虑这棵树（这样我们就有了一个具体的例子可以参考）：

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

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

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

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

使用迭代器和堆栈的二叉搜索树 in-order 遍历 - SPACE 复杂度 O(log N)？如何？

Binary Search Tree in-order traversal using Iterator & Stack - SPACE complexity O(log N)? How?

algorithm

binary-tree

binary-search-tree