使用迭代器的二叉树有序遍历&栈空间复杂度O(log )？多么?
在电话采访中，我被要求使用迭代器和堆栈(而不是递归)实现二进制搜索树的顺序遍历。不允许我使用父指针。
这是我得到的起始代码。
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 )”。我问他怎么做，他说“我们只需要存储父母”。(我可能听错了。他有很重的口音。)我的实现是存储所有离开子节点的节点。我只是认为他的回答是理所当然的。
然而，在面试之后，我认为，即使我们只需要存储父节点(而不是叶节点)，它仍然是O(N)。它是精确的O(N/2)，但它仍然是O(N)。我相信任何留下了子的节点都应该存储在堆栈中。怎么不这样做呢？
只有当二叉树只有一个不断向下的分支(不是具有完整叶子的平衡树)时，才能达到空间O(logN)。
这里我漏掉了什么？如果有人能解释如何使用迭代器将空间复杂度进一步降低到O(log )，我将不胜感激！
回答 2
Stack Overflow用户
发布于 2019-04-15 04:16:02
我想我能理解你的困惑。
考虑这棵树(只是为了让我们有一个具体的例子可供参考)：
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)个额外空间，因为您可以随着时间的推移重用空间。这就是使用堆栈的意义所在:您可以从顶部弹出一个元素，然后将一个新元素推入其位置。
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)空间的复杂性。
https://stackoverflow.com/questions/55678420
复制相似问题
腾讯云开发者
