欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 173. 二叉搜索树迭代器

程序员文章站 2024-03-23 09:40:28
...

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
注意: next() 和hasNext() 操作的时间复杂度是O(1),并使用 O(h) 内存,其中 h 是树的高度。

  • 中序遍历一下存下每个点即可。
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {
    List<Integer> ans;
        int ct;
        int ed;
        public BSTIterator(TreeNode root) {
            ans=new ArrayList<>();
            dfs(root);
            ct=0;
            ed=ans.size();
        }
        public void dfs(TreeNode root){
            if(root==null){
                return;
            }
            if(root.left!=null)dfs(root.left);
            ans.add(root.val);
            if(root.right!=null)dfs(root.right);
        }

        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            if(ct!=ed){
                return true;
            }
            return false;
        }

        /** @return the next smallest number */
        public int next() {
            return ans.get(ct++);
        }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */