LeetCode173 / LintCode 86 Binary Search Tree Iterator

思路

next使用bst的迭代版中序遍历
初始化和next基本组成了bst迭代版的中序遍历

复杂度

hasNext, next时间复杂度O(1)
空间复杂度O(1)

代码

/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }* Example of iterate a tree:* BSTIterator iterator = new BSTIterator(root);* while (iterator.hasNext()) {* TreeNode node = iterator.next();* do something for node* } */public class BSTIterator {
    private Stack<TreeNode> stack;/** @param root: The root of binary tree.*/public BSTIterator(TreeNode root) {
    // do intialization if necessarystack = new Stack<>();while (root != null) {
    stack.push(root);root = root.left;}}/** @return: True if there has next node, or false*/public boolean hasNext() {
    // write your code herereturn !stack.isEmpty();}/** @return: return next node*/public TreeNode next() {
    // write your code hereTreeNode cur = stack.peek();TreeNode node = cur;if (node.right == null) {
    node = stack.pop();while (!stack.isEmpty() && stack.peek().right == node) {
    node = stack.pop();}} else {
    node = node.right;while (node != null) {
    stack.push(node);node = node.left;}}return cur;}
}