173.【二叉搜索树迭代器】

简介: 173.【二叉搜索树迭代器】

正文


一、题目描述#

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

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


3.png



BSTIterator iterator = new BSTIterator(root);
iterator.next();    // 返回 3
iterator.next();    // 返回 7
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 9
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 15
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 20
iterator.hasNext(); // 返回 false


提示:

next() 和 hasNext() 操作的时间复杂度是 O(1),并使用 O(h) 内存,其中 h 是树的高度。你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 中至少存在一个下一个最小的数。


二、书写代码#


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {
    /**
     * 节点
     */
    private class Node {
        Node next;
        int val;
        public Node(int val) {
            this.val = val;
        }
    }
    private Node head = null, cur = null;
    private void preListNodeFromTree(TreeNode root) {
        if (root != null) {
            preListNodeFromTree(root.left);
            if (cur == null) {
                head = new Node(root.val);
                cur = head;
            } else {
                cur.next = new Node(root.val);
                cur = cur.next;
            }
            preListNodeFromTree(root.right);
        }
    }
    public BSTIterator(TreeNode root) {
        preListNodeFromTree(root);
    }
    /**
     * @return the next smallest number
     */
    public int next() {
        if (hasNext()) {
            int val = head.val;
            head = head.next;
            return val;
        }
        return -1;
    }
    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        return head != null;
    }
}
/**
 * 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.png

相关文章
|
6月前
【数据结构】二叉树的三种遍历(非递归讲解)
【数据结构】二叉树的三种遍历(非递归讲解)
55 1
|
6月前
|
算法 C++ 索引
分享一个关于Avl树的迭代器算法
该文介绍了无parent指针的AVL树迭代实现,提出了一种仅使用少量栈空间的双向迭代算法。算法分为初始化、前向迭代和后向迭代三部分。初始化时,根据起始点(最小或最大值)填充栈,然后根据状态进行前向或后向迭代。前向迭代检查当前节点的右子节点,后向迭代检查左子节点。算法通过堆栈维持双向迭代,解决了节点丢失和失序问题。此外,还讨论了算法在多线程环境下的同步问题和可能的解决方案。
|
12月前
|
算法 C++
C++二叉搜索树中第K小的元素
C++二叉搜索树中第K小的元素
|
存储 算法
二叉树的三序遍历
简要介绍二叉树的三序遍历和重构和代码实现。
101 0
|
存储 Java
二叉树的迭代器手写实现
二叉树的迭代器手写实现
二叉树的实现(前中后层序四种遍历)
二叉树的实现(前中后层序四种遍历)
54 0
二叉树四种遍历的实现
二叉树四种遍历的实现
100 0
|
iOS开发
二叉树非递归前中后遍历
因为个人身体原因,本周都在医院住院治疗身体,身边没有电脑,只能分享一些这周看过的比较好的书籍内容。iPad上传csdn图片顺序会有误,看书的页码就好。
二叉树非递归前中后遍历