题目：
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.
Example:
BSTIterator iterator = new BSTIterator(root); iterator.next(); // return 3 iterator.next(); // return 7 iterator.hasNext(); // return true iterator.next(); // return 9 iterator.hasNext(); // return true iterator.next(); // return 15 iterator.hasNext(); // return true iterator.next(); // return 20 iterator.hasNext(); // return false
Note:
next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.跟中序遍历差不多。第一个想法就是先中序遍历把结果存成一个list然后去get就完事了，但题目要求了空间复杂度O(h)，而存起来需要O(n)，显然不够efficient。于是就只能用一个stack来模拟整个遍历过程，每次取stack top就行。整体的思路就是先使劲push左边的节点，pop出来的时候看看它有没有右子节点，有的话就把它加进去。
Runtime: 14 ms, faster than 99.62% of Java online submissions for Binary Search Tree Iterator.
Memory Usage: 44 MB, less than 5.37% of Java online submissions for Binary Search Tree Iterator.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class BSTIterator { Deque<TreeNode> stack; public BSTIterator(TreeNode root) { stack = new ArrayDeque<>(); pushLeft(root); } private void pushLeft(TreeNode root) { TreeNode curr = root; while (curr != null) { stack.push(curr); curr = curr.left; } } /** @return the next smallest number */ public int next() { TreeNode node = stack.pop(); if (node.right != null) { pushLeft(node.right); } return node.val; } /** @return whether we have a next smallest number */ public boolean hasNext() { return !stack.isEmpty(); } } /** * 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(); */
