LeetCode173. 二叉搜索树迭代器

拼搏现实的明天。 2022-05-09 04:58 154阅读 0赞

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 `next()` 将返回二叉搜索树中的下一个最小的数。

注意:`next()` 和`hasNext()` 操作的时间复杂度是O(1)，并使用 *O(h)* 内存，其中 *h* 是树的高度。

--------------------

思路：因为BST后续遍历的结果为从大到小的排序，因此定义一个栈结构stack来存储BST后序遍历的结果，当取出栈顶元素时始终为最小元素。

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    public class BSTIterator {
    
        private ArrayDeque<Integer> stack=new ArrayDeque<Integer>();//用来保存二叉搜索树的深度优先遍历结果结点值
        public BSTIterator(TreeNode root) {
            dfs(root,stack);//将深度优先遍历BST的结果存入stack
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            if(!stack.isEmpty())
            return true;
            return false;
        }
    
        /** @return the next smallest number */
        public int next() {
            return stack.pop();
        }
    
        public void dfs(TreeNode root,ArrayDeque<Integer> stack){
            if(root==null){
                return ;
            }
            if(root.right!=null){
                dfs(root.right,stack);
            }
      //      System.out.println(root.val);
            stack.push(root.val);
            if(root.left!=null){
                dfs(root.left,stack);
            }
        }
    }
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = new BSTIterator(root);
     * while (i.hasNext()) v[f()] = i.next();
     */