`

Binary Search Tree Iterator

阅读更多
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

一道设计题,让我们设计一个数据结构,next方法返回二叉搜索树中最小的元素,hasNext方法判断是否还有元素,时间复杂度为O(1), 空间复杂为O(h), h为二叉树的高度。空间复杂度为h是给我们很好的提示,我们可以用堆栈来只存储左子树,这样就能保证空间复杂度为O(h)。每当next操作之后,我们检查当前节点的右子树是否为空,如果不为空就把右子树中的左子树压栈,这样在next操作时动态更新堆栈的内容。hasNext方法在堆栈为空的时候返回false,不为空的时候返回true。代码如下:
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {
    private Stack<TreeNode> stack;
    
    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();
        while(root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(stack.isEmpty()) return false;
        return true;
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode cur = stack.pop();
        int result = cur.val;
        cur = cur.right;
        while(cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        return result;
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */
1
0
分享到:
评论

相关推荐

    js-leetcode题解之173-binary-search-tree-iterator.js

    javascript js_leetcode题解之173-binary-search-tree-iterator.js

    LeetCode最全代码

    * [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...

    leetcode

    例如,LeetCode中的“Two Sum”问题就是一个经典的二分查找应用,而“Binary Search Tree Iterator”则涉及到对二叉搜索树的遍历,这些都是Java开发者在实际工作中可能遇到的问题。 在数据结构方面,LeetCode涵盖了...

    C++ tree 树 结构

    5. **排序树**:如二叉搜索树(Binary Search Tree, BST),其中每个节点的左子树只包含小于当前节点的值,右子树包含大于当前节点的值。这使得查找、插入和删除操作的时间复杂度为O(log n)。 6. **迭代器...

    STL源码剖析.pdg

    5.1.2 平衡二元搜寻树(balanced binary search tree) 203 5.1.3 avl tree(adelson-velskii-landis tree) 203 5.1.4 单旋转(single rotation) 205 5.1.5 双旋转(double rotation) 206 5.2 rb-tree(红黑...

    STL 源码剖析(侯捷先生译著)

    5.1.2 平衡二元搜寻树(balanced binary search tree) 203 5.1.3 AVL tree(Adelson-Velskii-Landis tree) 203 5.1.4 单旋转(Single Rotation) 205 5.1.5 双旋转(Double Rotation) 206 5.2 RB-tree(红黑...

    数据结构 二叉树原程序

    本篇文章将深入探讨一个C++语言实现的二叉搜索树(Binary Search Tree, BST)的程序代码。该程序定义了一个通用模板类`BinSearchTree`,用于表示二叉搜索树,并提供了基本的操作功能,如插入、删除以及遍历等。通过...

    数据结构与算法(JAVA语言版)-中文

    - **AVL树**:介绍AVL树(self-balancing binary search tree),解释如何通过旋转(rotation)保持树的平衡。 - **B-树**:讲解B-树(B-tree)的定义,包括分裂(splitting)和合并(merging)等操作。 - **哈希** - **...

    数据结构和Java集合框架 英文版 第三版

    - 二叉搜索树(Binary Search Tree) - 平衡二叉树(AVL Tree) - 红黑树(Red-Black Tree) - B树(B-Tree) - 字典树(Trie) - **图(Graph)**:由顶点和边组成的非线性数据结构,用于表示对象之间的复杂关系。 - 无...

    222020321062106_温长锟72

    二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树,其中每个节点的左子树只包含比它小的元素,右子树只包含比它大的元素。这确保了对树的搜索、插入和删除操作具有高效的性能。 2. 熟悉在二叉搜索树上执行...

    思考题 1

    在这个场景中,虽然没有直接使用代理类,但可以想象如果需要为`BinaryTree`类添加额外的功能,如权限控制、日志记录等,可以创建一个代理类来包裹`BinaryTree`,代理类在调用实际操作之前执行这些附加任务。...

    javaarraylist源码-Data-Structures-Algorithms:使用Java编程语言的数据结构和算法源代码(包括Stac

    10. **Binary Tree**:二叉树是一种重要的数据结构,包括二叉搜索树(Binary Search Tree)、平衡二叉树(AVL、Red-Black Tree等),它们在搜索、排序等方面有着广泛应用。 通过研究这些源代码,开发者可以深入理解...

    Lintcode-java版本

    - Binary Tree(二叉树):涉及二叉树的遍历、深度、插入、搜索等基本操作。 - Binary Search(二分搜索):一种有效的查找算法,在有序数组中查找特定元素。 - Search in Rotated Sorted Array(旋转排序数组中的...

    javalruleetcode-leetcode-python:leetcode问题的Python解决方案

    Iterator.用一个stack存,对每一个nestedlist进行开苞,用递归或者while循环判断是否第一个element 的isInteger()是否是True. 4.10 812题. Largest Triangle Area.数学问题,已知三点求三角形面积,公式为Helen ...

    Cpp_code:c学习c ++历程中模拟实现关于STL容器,特殊类,智能指针以及一些高阶的数据结构

    - **树(Tree)**:如二叉查找树(Binary Search Tree)、平衡树(AVL Tree、Red-Black Tree)等,用于高效搜索和排序操作。 - **图算法**:如Dijkstra最短路径算法、Floyd-Warshall所有路径算法等。 在"Cpp_code-master...

    树莓派交叉编译工具链百度盘下载_永久有效.txt

    │ │ │ │ │ ├─bin_search_tree_ │ │ │ │ │ ├─branch_policy │ │ │ │ │ ├─cc_hash_table_map_ │ │ │ │ │ ├─eq_fn │ │ │ │ │ ├─gp_hash_table_map_ │ │ │ │ │ ├─...

    java数据结构源码-dataStructure_java:学习《数据结构与抽象Java描述》源码与总结

    二叉树是每个节点最多有两个子节点的树,常见的有二叉查找树(Binary Search Tree, BST)。 7. **哈希表(HashMap)**: - 哈希表通过哈希函数快速定位元素,提供了高效的查找、插入和删除操作。Java中的`java....

    java错误提示英汉对照

    - **Binary search二分搜寻法/二分查找**:在有序数组中搜索一个元素的有效算法,时间复杂度为O(log n)。 - **Binary tree二元树/二叉树**:一种数据结构,每个节点最多有两个子节点。 以上就是基于给定文件中的...

Global site tag (gtag.js) - Google Analytics