LeetCode 173.Binary Search Tree Iterator (二叉搜索树迭代器)

àì夳堔傛蜴生んèń 2022-04-15 00:21 156阅读 0赞

题目描述：

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

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

注意:`next()` 和`hasNext()` 操作的时间复杂度是O(1)，并使用 *O(h)* 内存，其中 *h* 是树的高度。

AC C++ Solution:

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class BSTIterator {
    public:
        stack<TreeNode *> stk;
        BSTIterator(TreeNode *root) {   //构造函数:把所有左节点压入栈
            while(root) {
                stk.push(root);
                root = root->left;
            }
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !stk.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode *pop = stk.top();
            stk.pop();
            int res = pop->val;
            if(pop->right) {
                TreeNode *root = pop->right;    
                while(root) {               
                    stk.push(root);
                    root = root->left;
                }
            }
            
            return res;
        }
    };
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = BSTIterator(root);
     * while (i.hasNext()) cout << i.next();
     */

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode173.二叉搜索树迭代器

题目描述: 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用 next() 将返回二叉搜索树中的下一个最小的数。示例： ![3154746c5

小咪咪/ 2022年12月21日 06:26/ 0 赞/ 136 阅读

相关 173. 二叉搜索树迭代器

题目来源 [173. 二叉搜索树迭代器][173.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_s

「爱情、让人受尽委屈。」/ 2022年12月21日 06:17/ 0 赞/ 120 阅读

相关 Binary Search Tree Iterator（C++二叉搜索树迭代器）

解题思路：（1）中序遍历 / Definition for a binary tree node. struct TreeNode {

柔情只为你懂/ 2022年11月19日 01:10/ 0 赞/ 142 阅读

相关 LeetCode 173. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器： BSTIterator(TreeNode root) 初始化 BSTI

电玩女神/ 2022年11月14日 10:27/ 0 赞/ 143 阅读

相关 LeetCode173. 二叉搜索树迭代器

难度：中等题目描述： > 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器： > BSTIterator(Tree

旧城等待，/ 2022年11月14日 10:15/ 0 赞/ 136 阅读

相关 LeetCode173-Binary Search Tree Iterator

LeetCode 173 : Binary Search Tree Iterator Implement an iterator over a binary search t

女爷i/ 2022年08月04日 12:48/ 0 赞/ 5 阅读

相关 leetcode 173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized

红太狼/ 2022年07月26日 00:25/ 0 赞/ 136 阅读

相关 LeetCode173—Binary Search Tree Iterator

原题 [原题链接][Link 1] > Implement an iterator over a binary search tree (BST). Your iter

骑猪看日落/ 2022年07月14日 06:26/ 0 赞/ 148 阅读

相关 LeetCode173. 二叉搜索树迭代器

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用 `next()` 将返回二叉搜索树中的下一个最小的数。注意:`next()` 和`hasNext

拼搏现实的明天。/ 2022年05月09日 04:58/ 0 赞/ 163 阅读

相关 LeetCode 173.Binary Search Tree Iterator (二叉搜索树迭代器)

题目描述：实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用 `next()` 将返回二叉搜索树中的下一个最小的数。注意:`next()` 和`

àì夳堔傛蜴生んèń/ 2022年04月15日 00:21/ 0 赞/ 157 阅读