本文共 1970 字，大约阅读时间需要 6 分钟。

链接：

大意：

构造一棵BST的迭代器，迭代器通过往构造函数传入树根节点得到，实现迭代器的两个函数next()和hasNext()，用于获得迭代器的下一个元素以及判断是否有下一个元素。例子：

思路：

在构造迭代器时（构造函数内），使用一个list存储BST中序遍历，并设置一个实例域currIdx为当前遍历到迭代器的位置，另一个实例域size为BST中序遍历的长度。具体代码如下。

代码：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class BSTIterator {    private ArrayList
   
     order = new ArrayList<>();    private int currIdx;    private int size;    public BSTIterator(TreeNode root) {        inOrder(root);        currIdx = -1;        size = order.size();    }        /** @return the next smallest number */    public int next() {        if (hasNext())            return order.get(++currIdx);        return -1; // 表示不存在下一个元素    }        /** @return whether we have a next smallest number */    public boolean hasNext() {        return currIdx < size - 1;    }        private void inOrder(TreeNode root) {        if (root == null)            return ;        inOrder(root.left);        order.add(root.val);        inOrder(root.right);    } }/** * 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(); */
   

结果：

结论：

next()和hasNext()的时间复杂度均为O(1)。使用的空间复杂度为O(n)，n为树节点的个数。题目最后的提示是最优解法的空间复杂度为O(h)，h为树的高度。有待改进。。。

最佳：

class BSTIterator {    LinkedList
   
     st;    public BSTIterator(TreeNode root) {        st = new LinkedList<>();        while (root != null) {            st.offerFirst(root);            root = root.left;        }    }        public int next() {        int val = st.peekFirst().val;        TreeNode n= st.pollFirst();        TreeNode r = n.right;        while (r!=null) {            st.offerFirst(r);            r = r.left;        }        return val;    }        public boolean hasNext() {        return !st.isEmpty();    }}
   

方法确实巧妙。首先存储左斜枝的节点值，待next拿掉一个当前最小的节点后，将被拿节点的右子树作为新的root，将root以及的左斜枝添加到list首部中。 

转载地址：http://waesi.baihongyu.com/