- 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.
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class BSTIterator {
- private LinkedList<TreeNode> stack;
- private TreeNode cur;
- public BSTIterator(TreeNode root) {
- stack = new LinkedList<>();
- cur = root;
- }
- /** @return the next smallest number */
- public int next() {
- while (cur != null) {
- stack.offerFirst(cur);
- cur = cur.left;
- }
- cur = stack.pollFirst();
- int val = cur.val;
- cur = cur.right;
- return val;
- }
- /** @return whether we have a next smallest number */
- public boolean hasNext() {
- return !stack.isEmpty() || cur != null;
- }
- }
- /**
- * Your BSTIterator object will be instantiated and called as such:
- * BSTIterator obj = new BSTIterator(root);
- * int param_1 = obj.next();
- * boolean param_2 = obj.hasNext();
- */
- [LC] 173. Binary Search Tree Iterator
来源: http://www.bubuko.com/infodetail-3382346.html