173. 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.Example:BSTIterator iterator = new BSTIterator(root);iterator.next(); // return 3iterator.next(); // return 7iterator.hasNext(); // return trueiterator.next(); // return 9iterator.hasNext(); // return trueiterator.next(); // return 15iterator.hasNext(); // return trueiterator.next(); // return 20iterator.hasNext(); // return falseNote: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.难度：medium题目：实现二叉搜索树的遍历。迭代器用根结点初始化。调用next()将会返回下一个最小的结点。Runtime: 76 ms, faster than 37.23% of Java online submissions for Binary Search Tree Iterator.Memory Usage: 52.1 MB, less than 100.00% 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(int x) { val = x; } * } /class BSTIterator { private Stack<TreeNode> stack; public BSTIterator(TreeNode root) { stack = new Stack<>(); while (root != null) { stack.push(root); root = root.left; } } /* @return the next smallest number / public int next() { TreeNode node = stack.pop(); TreeNode ptr = node.right; while (ptr != null) { stack.push(ptr); ptr = ptr.left; } 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(); */