`

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
分享到:
评论

相关推荐

    cpp-算法精粹

    Binary Search Tree Iterator Binary Tree Zigzag Level Order Traversal Recover Binary Search Tree Same Tree Symmetric Tree Balanced Binary Tree Flatten Binary Tree to Linked List Populating Next Right ...

    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]...

    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(红黑...

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

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

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

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

    Python Cookbook英文版

    2.5 Looking for Items in a Sorted Sequence Using Binary Search 2.6 Sorting a List of Objects by an Attribute of the Objects 2.7 Sorting by Item or by Attribute 2.8 Selecting Random Elements ...

    BobBuilder_app

    This means that you do a binary search in the page list in log M time and get the value in O(1) time within a page. RaptorDB starts off by loading the page list and it is good to go from there and...

    Python Cookbook, 2nd Edition

    Swapping One File Extension for Another Throughout a Directory Tree Recipe 2.18. Finding a File Given a Search Path Recipe 2.19. Finding Files Given a Search Path and a Pattern Recipe 2.20. ...

    Git-2.21.0-64-bit.zip

    * Adjust the dir-iterator API and apply it to the local clone optimization codepath. * We have been trying out a few language features outside c89; the coding guidelines document did not talk ...

    python3.6.5参考手册 chm

    PEP 471 - os.scandir() function – a better and faster directory iterator PEP 475: Retry system calls failing with EINTR PEP 479: Change StopIteration handling inside generators PEP 485: A function...

Global site tag (gtag.js) - Google Analytics