LeetCode173 Binary Search Tree Iterator

最新推荐文章于 2023-02-25 23:52:55 发布

_IanXiao

最新推荐文章于 2023-02-25 23:52:55 发布

阅读量396

点赞数

分类专栏： LeetCode 树文章标签： leetcode 173 树中序遍历非递归

本文链接：https://blog.csdn.net/codeTZ/article/details/50445626

版权

LeetCode 同时被 2 个专栏收录

87 篇文章

订阅专栏

树

21 篇文章

订阅专栏

本文介绍了一种实现二叉搜索树迭代器的方法，通过使用栈来存储节点，并利用中序遍历的思想，实现了next()和hasNext()两个关键方法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接：

https://leetcode.com/problems/binary-search-tree-iterator/

题目描述：

天啦撸QAQ，整了半天都没懂起题目是几个意思。最后的最后，才明白大概是按中序遍历把节点非递归输出。

题目分析：

中序遍历的非递归的变形。大概方向就是用栈，将最左边的节点压入栈中。next() 就是弹出栈顶元素。
需要注意的是，被弹出的元素如果有右节点时，将右节点及右节点最左边的节点压入栈中。

代码：

class BSTIterator {
public:
    stack<TreeNode*> s;
    BSTIterator(TreeNode *root) {
        while(!s.empty()){
            s.pop();
        }
        while(root!=NULL){
            s.push(root);
            root=root->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    int next() {
        TreeNode* top=s.top();
        TreeNode* ptr=top;
        s.pop();
        if(ptr->right!=NULL){
            ptr=ptr->right;
            while(ptr!=NULL){
                s.push(ptr);
                ptr=ptr->left;
            }
        }
        return top->val;
    }
};