leetcode173.二叉搜索树迭代器

小咪咪 2022-12-21 06:26 132阅读 0赞

题目描述:

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

![3154746c5e53726cc5509e015807ae35.png][]

BSTIterator iterator = new BSTIterator(root);  
iterator.next(); // 返回 3  
iterator.next(); // 返回 7  
iterator.hasNext(); // 返回 true  
iterator.next(); // 返回 9  
iterator.hasNext(); // 返回 true  
iterator.next(); // 返回 15  
iterator.hasNext(); // 返回 true  
iterator.next(); // 返回 20  
iterator.hasNext(); // 返回 false

提示：

next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。  
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

算法思路:因为该问题提示next和hasNext使用的时间空间复杂度为 O(h),而二叉搜索树的性质是中序遍历是一个升序序列,所以我们自然想到采用中序遍历解决此问题

我们可以采用手动写中序递归(受控递归)的思想,当我们找到树的第一个结点后暂停递归,然后没输出一个结点才开始进行下一个结点的查找,该过程可以用一个模拟栈实现

因此,我们可以写一个函数is\_next判断栈顶是不是我们需要的下一个结点,如果不是那么可以采用此函数寻找下一个结点

class BSTIterator {
    public:
        BSTIterator(TreeNode* root) {
           /*if(!root) return;
           //尝试对搜索树进行深度拷贝
           bin_root=new TreeNode(root->val); 
           bin_root->left=copy(root->left);
           bin_root->right=copy(root->right);*/
    
           //进行线索树
           /*TreeNode *pre=bin_root;
           TreeNode *cur_node=bin_root;
            while(cur_node){
                while(cur_node->left){
                    pre=cur_node->left;
                    while(pre->right && pre->right!=cur_node) pre=pre->right;
                    if(pre->right!=cur_node) {
                        pre->right=cur_node;
                        cur_node=cur_node->left;
                    }
                    else{
                        cur_node=cur_node->right;
                    }
                }
                cur_node=cur_node->right;
            }*/
    
            while(!is_next(root)) root=root->left;
        }
        
        /** @return the next smallest number */
        int next() {
            TreeNode *tem=s.top();
            TreeNode *tem1=tem->right;
            s.pop();
            while(!is_next(tem1)) tem1=tem1->left;
            return tem->val;
        }
        
        /** @return whether we have a next smallest number */
        bool hasNext() {
            if(!s.empty()) return true;
            else return false;
        }
    private:
        stack<TreeNode *> s;
        bool is_next(TreeNode *cur_node){ //用来判断堆栈顶部是否为下一个结点
            if(!cur_node) return true;
            else{
                s.push(cur_node);
                return false;
            }
        }
    //开始向对树进行深度拷贝
        /*TreeNode *copy(TreeNode *node){
            if(!node) return NULL;
            bin_node=new TreeNode(node->val);
            bin_node->left=copy(node->left);
            bin_node->right=copy(node->right);
            return node;
        }*/
    };

我们可以分析一下他的空间复杂度为O(h)时间,在这棵树相对平衡的情况下时间复杂度大致为O(1)

[3154746c5e53726cc5509e015807ae35.png]: /images/20221120/38c25353facf4a7bb2e3fd9682fd517b.png