LeetCode_数据结构设计_中等_173.二叉搜索树迭代器

￡神魔★判官ぃ 2023-10-12 11:51 29阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

*  BSTIterator(TreeNode root)：初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
 *  boolean hasNext()：如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
 *  int next()：将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

**示例：**

![在这里插入图片描述][1ece10cdddc24f3eb701cfdab1cd4db1.png]

输入
    ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
    [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
    输出
    [null, 3, 7, true, 9, true, 15, true, 20, false]
    解释
    BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
    bSTIterator.next();    // 返回 3
    bSTIterator.next();    // 返回 7
    bSTIterator.hasNext(); // 返回 True
    bSTIterator.next();    // 返回 9
    bSTIterator.hasNext(); // 返回 True
    bSTIterator.next();    // 返回 15
    bSTIterator.hasNext(); // 返回 True
    bSTIterator.next();    // 返回 20
    bSTIterator.hasNext(); // 返回 False

提示：  
树中节点的数目在范围 \[1, 105\] 内  
0 <= Node.val <= 106  
最多调用 105 次 hasNext 和 next 操作

**进阶：**  
你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/binary-search-tree-iterator

## 2.思路 ##

（1）扁平化

（2）迭代

## 3.代码实现（Java） ##

//思路1————扁平化
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class BSTIterator {
        
    
        private int idx;
        private List<Integer> nums;
    
        public BSTIterator(TreeNode root) {
        
            idx = 0;
            nums = new ArrayList<>();
            inorderTraversal(root, nums);
        }
        
        public int next() {
        
            return nums.get(idx++);
        }
        
        public boolean hasNext() {
          
            return idx < nums.size();
        }
    
        //前序遍历，并将遍历到的节点值依次存储到 nums 中
        private void inorderTraversal(TreeNode root, List<Integer> nums) {
        
            if (root == null) {
        
                return;
            }
            inorderTraversal(root.left, nums);
            nums.add(root.val);
            inorderTraversal(root.right, nums);
        }
    }
    
    /**
     * 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();
     */

//思路2————迭代
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class BSTIterator {
        
        private TreeNode cur;
        private Deque<TreeNode> stack;
    
        public BSTIterator(TreeNode root) {
        
            cur = root;
            stack = new LinkedList<TreeNode>();
        }
        
        public int next() {
        
            while (cur != null) {
        
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            int ret = cur.val;
            cur = cur.right;
            return ret;
        }
        
        public boolean hasNext() {
        
            return cur != null || !stack.isEmpty();
        }
    }
    
    /**
     * 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();
     */

[1ece10cdddc24f3eb701cfdab1cd4db1.png]: https://img-blog.csdnimg.cn/1ece10cdddc24f3eb701cfdab1cd4db1.png