Leetcode复习小结Tree

Preorder Iterator

class BSTIterator {    Stack<TreeNode> s = new Stack<>();    public BSTIterator(TreeNode root) {        if (root != null)   s.push(root);    }        public int next() {        TreeNode cur = s.pop();        if (cur.right != null)  s.push(cur.right);        if (cur.left != null)   s.push(cur.left);        return cur.val;    }        public boolean hasNext() {        return (!s.isEmpty());    }}

Postorder Iterator

class BSTIterator {    Stack<TreeNode> s = new Stack<>();    public BSTIterator(TreeNode root) {        push(root);    }        public int next() {        TreeNode cur = s.pop();        if (!s.isEmpty()) {            TreeNode top = s.peek();            if (cur == top.left)                push(top.right);        }        return cur.val;    }     public boolean hasNext() {        return (!s.isEmpty());    }        public void push(TreeNode node) {        while (node != null) {            s.push(node);            if (node.left != null)                node = node.left;            else    node = node.right;        }    }}

Inorder Iterator

class BSTIterator {    Stack<TreeNode> s = new Stack<>();    public BSTIterator(TreeNode root) {        push(root);    }        /** @return the next smallest number */    public int next() {        TreeNode cur = s.pop();        push(cur.right);        return cur.val;    }        /** @return whether we have a next smallest number */    public boolean hasNext() {        return !s.isEmpty();    }    public void push(TreeNode node) {        while (node != null) {            s.push(node);            node = node.left;        }    }}