- 浏览: 171798 次
- 性别:
- 来自: 济南
文章分类
最新评论
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。代码如下:
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(); */
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 221Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 219You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 336Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 325Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 443Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 499Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 423Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 611Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 421The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 378Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 511Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 522Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 364All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 853Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 876Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 547Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 592Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 757Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 724You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 623For a undirected graph with tre ...
相关推荐
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 ...
* [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]...
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(红黑...
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(红黑...
Iterator.用一个stack存,对每一个nestedlist进行开苞,用递归或者while循环判断是否第一个element 的isInteger()是否是True. 4.10 812题. Largest Triangle Area.数学问题,已知三点求三角形面积,公式为Helen ...
│ │ │ │ │ ├─bin_search_tree_ │ │ │ │ │ ├─branch_policy │ │ │ │ │ ├─cc_hash_table_map_ │ │ │ │ │ ├─eq_fn │ │ │ │ │ ├─gp_hash_table_map_ │ │ │ │ │ ├─...
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 ...
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...
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. ...
* 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 ...
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...