代码编织梦想

题目

剑指 Offer II 055. 二叉搜索树迭代器
在这里插入图片描述

思路

解决这个问题有很多种不同的方法:

允许修改二叉树

如果允许修改输入的二叉搜索树,则可以在初始化迭代器时将它展平成除叶节点之外其他节点只有一个右子节点。这时二叉搜索树看起来像一个链表。然后用一个指针P指向展平后的二叉搜索树的根节点,如果指针P指向的节点不为null,那么函数hasNext将返回true。每次函数next被调用时都返回指针P指向节点的值,并将指针P朝着指向右子节点的指针向前移动一次

  • 空间复杂度:如果按照中序遍历的顺序将二叉搜索树展平,那么展平的过程中需要一个大小为O(h)的栈
  • 缺点:需要修改原有结构

预先将节点放到链表中

如果不允许修改输入的二叉搜索树,那么可以在迭代器初始化时另外创建一个链表保存二叉树所有节点的值。还是按照中序遍历的顺序遍历二叉搜索树,每遍历到一个节点就在链表中插入与树中节点的

然后将指针P指向链表的头节点,接下来函数hasNext和next的执行过程与前一种方法一样。在完成迭代器的初始化之后,链表中将包含n个节点。这个链表在初始化完成之后一直存在

  • 缺点:空间复杂度较高,为O(n),因为需要将所有节点或元素预先保存到list

原地遍历

可以在不修改输入的二叉搜索树的同时优化空间效率

在非递归遍历的过程中:

  • hasNext: 根据stack是否不为空,判断是否有下一个元素
  • next: 用正常的方式取出下一个元素

这种做法能做到既不修改原有树,也让空间复杂度降为 O(h) ,即数的高度量级

代码


class BSTIterator {
    static class Command{
        public String commond;
        public TreeNode treeNode;
        public Command(String com,TreeNode node){
            this.commond = com;
            this.treeNode = node;
        }
    }
        
    private Stack<Command> stack;

    public BSTIterator(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        stack = new Stack<>();
        stack.push(new Command("go",root));
    }

    public int next() {
        while (!stack.isEmpty()) {
            Command pop = stack.pop();
            if ("go".equals(pop.commond)) {
                if (pop.treeNode.right != null) {
                    stack.push(new Command("go", pop.treeNode.right));
                }
                stack.push(new Command("collect", pop.treeNode));
                if (pop.treeNode.left != null) {
                    stack.push(new Command("go", pop.treeNode.left));
                }

            } else {
                return pop.treeNode.val;
            }
        }
        return 0;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39383767/article/details/127957530

173. 二叉搜索树迭代器;剑指 Offer 38. 字符串的排列-爱代码爱编程

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * Tre

【树-中等】剑指 Offer II 055. 二叉搜索树迭代器-爱代码爱编程

【题目】 实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器: BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。 bo

剑指offer55:二叉搜索树迭代器-爱代码爱编程

题目: 实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器: BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。 bool

剑指offer_055 二叉搜索树迭代器-爱代码爱编程

题目: 实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器: BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素

剑指offer 专项突破版 55、二叉搜索树迭代器-爱代码爱编程

题目链接 思路一 先中序遍历把所有结点放入队列,然后在调用next函数时pop队头即可 class BSTIterator { Queue<TreeNode> queue; public BSTIterator(TreeNode root) { queue = new LinkedLi

剑指offer 专项突破版 56、二叉搜索树中两个节点之和-爱代码爱编程

题目链接 思路一 这道题在数组中做过类似的~,所以自然就想到先中序遍历变成数组,然后用双指针做,这样的话需要两次遍历,如果在遍历的过程中搭配哈希表,那么遍历一次即可~ class Solution { public boolean findTarget(TreeNode root, int k) { Set&

剑指 Offer II 055. 二叉搜索树迭代器(中等 二叉搜索树 迭代器)-爱代码爱编程

剑指 Offer II 055. 二叉搜索树迭代器 实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器: BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字

剑指 offer ii 055. 二叉搜索树迭代器_qbnmm的博客-爱代码爱编程

题目链接 力扣 题目描述 实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器: BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于

leetcode 刷题日记 剑指 offer ii 055. 二叉搜索树迭代器_jetecho的博客-爱代码爱编程

原题链接(https://leetcode.cn/problems/kTOapQ/) 文章目录 题目描述示例 思路代码 题目描述 实现一个二叉搜索树迭代器类BSTIterator ,表示一个按

剑指 offer(专项突击版)- 剑指 offer ii 055. 二叉搜索树迭代器(20220802)_bupt-wt的博客-爱代码爱编程

实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器: BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。 boolean

【leetcode】【剑指offer Ⅱ】055. 二叉搜索树迭代器_cheny1li1998的博客-爱代码爱编程

问题描述: 实现一个二叉搜索树迭代器类 BSTIterator,表示一个按中序遍历二叉搜索树(BST)的迭代器: BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象,B

cas机制的的解释和总结_水岸齐天的博客-爱代码爱编程

文章目录 CAS是什么?有什么作用?CAS的工作原理?CAS的缺点?怎么解决ABA问题呢?CAS在虚拟机中的应用?CAS 性能优化 CAS是什么?有什么作用? 比较并交换(Compare-and-Swap

一个数组的异或和是指数组中所有的数异或在一起的结果,给定一个数组arr,求最大子数组异或和。_朂後 哋箹萣的博客-爱代码爱编程

问题描述:         一个数组的异或和是指数组中所有的数异或在一起的结果,给定一个数组arr,求最大子数组异或和。 异或运算规则:         异或也叫半加运算,其运算法则相当于不带进位的二进制加法:二进制下用1表示真,0表示假,则异或的运算法则为:0⊕0=0,1⊕0=1,0⊕1=1,1⊕1=0(同为0,异为1),这些法则与加法是相同的

骚戴独家笔试---算法篇_骚戴的博客-爱代码爱编程

链表 反转链表 /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ import java.util.Stack; public class Solution { public ListNo

图 知识点总结(王道)_小&苏的博客-爱代码爱编程

图的定义 图G由顶点集V和边集E组成,记为G=(V,E),其中V(G)表示图G中顶点的有限非空集;E(G)表示图G中顶点之间的关系(边)集合。若V={v1,v2vn},则用|V|表示图G中顶点的个数,也称图G的阶,E={(

320力扣周赛总结_yan扬的博客-爱代码爱编程

目录  一、三元组数目 二、二叉树最近结点查询 三、到达首都的最少油耗 四、完美分割的方案数  一、三元组数目 6241. 数组中不等三元组的数目https://leetcode.cn/problems/number-of-unequal-triplets-in-array/    思路:数据范围都非常小,三重循环即可,开胃小菜!