代码之家 › 专栏 › 技术社区 › aerin

二叉搜索树使用迭代器和栈空间复杂度O(log n)顺序遍历?怎么用?

binary-search-tree binary-tree algorithm

aerin · 技术社区 · 6 年前

在电话采访中,我被要求实现二进制搜索树,以便使用迭代器堆栈遍历( ). 不允许我使用父指针。

这是我得到的起始代码。

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(N/2),但仍然是O(N)。我相信 任何留下子节点的节点

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

我错过了什么?如果任何人可以解释如何使用迭代器的空间复杂度可以进一步降低到O(log n),我将非常感激!

0 回复 | 直到 6 年前

ruakh 6 年前

我想我理解你的困惑。

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

在遍历此树的过程中,您需要存储每个具有左子节点(三个节点)的节点 A B ,和 C . 一般来说,对于任何树,您都需要存储 ( n个 O型 ( n个 ).

但你不需要保留所有这些节点马上 E ,您不再需要保留节点为了什么。在迭代的任何给定点上,您只需要保持的祖先节点-最多有两个节点,即 一个 (当当前节点是 D ). 一般来说,对于任何一棵树,你永远不需要存储超过 ( 小时 )同时的节点,其中是树的高度。假设一棵平衡的树(你的面试官很清楚),这意味着 O型 n个 ).

O型 ( )额外的空间,因为你可以随着时间的推移重用空间。这就是使用堆栈的一点:可以从顶部弹出一个元素,然后将一个新元素推到它的位置。

Shridhar R Kulkarni 6 年前

如果二叉搜索树(BST)是不平衡的,我们必须使用堆栈方法,那么 O(h) 是空间的复杂性,在哪里 h 是给定BST的高度。显然,它是 不可能 如果要遵循栈方法,则要获得更好的空间复杂度。

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

显然,如果不强制使用堆栈方法,则可以围绕时间和空间复杂度进行权衡。如果允许预处理,则使用 Morris in-order traversal using threading O(n) 额外空间和 O(1) 时间复杂度。或者,如果不允许预处理,您可以只存储 current 特雷诺德。什么时候? next() O(对数) 平衡BST和in的时间 BST更新不平衡的时间 现在的 在返回之前 下一步() O(一) 空间复杂度。