二叉查找树迭代器

题目描述

设计实现一个带有下列属性的二叉查找树的迭代器：
元素按照递增的顺序被访问（比如中序遍历）
next()和hasNext()的询问操作要求均摊时间复杂度是O(1)

思路

递归遍历二叉树
1、new迭代器时遍历二叉查找树，遍历的顺序采取右序遍历。遍历的元素保存到Stack里
2、hasNext方法判断stack是否为空
3、next方法从stack里pop

代码

public class BSTIterator {
    //@param root: The root of binary tree.
    private Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        // write your code here
        stack = new Stack<>();
        addNode(root);
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        // write your code here
        return !stack.isEmpty();
    }
    
    private void addNode(TreeNode root) {
        if(root == null) {
            return;
        }
        addNode(root.right);
        stack.push(root);
        addNode(root.left);
    }
    
    //@return: return next node
    public TreeNode next() {
        // write your code here
        return stack.pop();
    }
}

考差点

• 二叉查找树