LeetCode——二叉搜索树迭代器

NO.173 二叉搜索树迭代器中等

思路一：栈 看到空间要求 O(h) 的时候，就可以大概想到是对树做递归，递归栈的大小取决于树的高度。

要求 next() 返回当前最小节点，如果一直调用直至树为空，应该返回一个递增序列，即 BST 的中序遍历。

树的定义：

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

迭代器：

public class BSTIterator {

    Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        this.inorder_left(root);
    }

    //遍历 root 最左节点入栈
    private void inorder_left(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /**
     * @return the next smallest number
     */
    public int next() {
        TreeNode node = stack.pop();
        if (node.right != null) {
            inorder_left(node.right);
        }
        return node.val;
    }

    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

时间复杂度：O(1) hasNext() 毋庸置疑的是个 O(1) 操作； next() 操作虽然有一个最坏情况(呈链表)下 O(n)的操作，但是每个节点只会入栈一次，所以 n 次 next() 操作平均下来时间复杂度依然是 O(1) ，这是一种”摊还”的概念。

空间复杂度：O(h) h 树的高度

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.173 二叉搜索树迭代器 中等

NO.173 二叉搜索树迭代器中等