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;
        }
    }
}