首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >使用迭代器的二叉树有序遍历&栈空间复杂度O(log )?多么?

使用迭代器的二叉树有序遍历&栈空间复杂度O(log )?多么?
EN

Stack Overflow用户
提问于 2019-04-15 02:05:01
回答 2查看 417关注 0票数 3

在电话采访中,我被要求使用迭代器和堆栈(而不是递归)实现二进制搜索树的顺序遍历。不允许我使用父指针。

这是我得到的起始代码。

代码语言:javascript
复制
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() {

    }

};

测试函数:

代码语言:javascript
复制
void TestFunc(TreeNode *root) {
BTIterator bti(root);
while(bti->hasNext()) {
  cout << bti->next()->val << " ";
}}

上面的代码特别要求我实现BTIteratornexthasNext

所以我就这么做了。后续问题是什么是时间和空间复杂性。所以我回答时间是O(N),空间是O(N)。然而,面试官说“你可以将空间复杂度进一步降低到O(log )”。我问他怎么做,他说“我们只需要存储父母”。(我可能听错了。他有很重的口音。)我的实现是存储所有离开子节点的节点。我只是认为他的回答是理所当然的。

然而,在面试之后,我认为,即使我们只需要存储父节点(而不是叶节点),它仍然是O(N)。它是精确的O(N/2),但它仍然是O(N)。我相信任何留下了子的节点都应该存储在堆栈中。怎么不这样做呢?

只有当二叉树只有一个不断向下的分支(不是具有完整叶子的平衡树)时,才能达到空间O(logN)。

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

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2019-04-15 04:16:02

我想我能理解你的困惑。

考虑这棵树(只是为了让我们有一个具体的例子可供参考):

代码语言:javascript
复制
         A
       /   \
      B     C
     / \   / \
    D   E F   G

在遍历此树的过程中,您将需要存储具有左子节点的每个节点-三个节点ABC。一般来说,对于任何树,您都需要在迭代过程中存储最多O(n)个节点。这似乎就是你说O(n)的原因。

但您不需要一次保留所有这些节点。一旦您向前迭代到E,就不再需要为任何东西保留节点B。在迭代中的任何给定点,您只需要保留当前节点的后续祖先-最多是两个节点,即AB (当当前节点为D时)。一般来说,对于任何树,您永远不需要同时存储超过O(h)个节点,其中h是树的高度。假设有一棵平衡树(正如你的面试官显然是这样),这意味着O(log-n)。

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

票数 3
EN

Stack Overflow用户

发布于 2019-04-15 03:56:01

如果二叉搜索树是不平衡的,我们必须使用堆栈方法,那么O(h)是空间复杂度,其中h是给定二叉搜索树的高度。显然,如果遵循堆栈方法,不可能达到更好的空间复杂度。

如果给定的BST是平衡的,或者如果允许您平衡它,那么就有可能实现O(logn)空间复杂度,其中n是给定BST中的节点数量。

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

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/55678420

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档