首页 > 其他分享 >173. 二叉搜索树迭代器

173. 二叉搜索树迭代器

时间:2023-11-30 15:55:05浏览次数:32  
标签:BSTIterator 迭代 int dfs st ans 二叉 173

173. 二叉搜索树迭代器

2021年3月28日

让你实现二叉搜索树的迭代器,实现中序遍历

\(next()\)返回元素,并使迭代器下移一个

\(hasnext()\)返回是否存在

两种方法,非递归和递归

递归写法

没啥难度,就普通的遍历,将数值存入 queue就是了

class BSTIterator {
  private:
    queue<int> q;

  public:
    BSTIterator(TreeNode *root) {
        dfs(root);
    }
    void dfs(TreeNode *p) {
        if (p) {
            dfs(p->left);
            q.push(p->val);
            dfs(p->right);
        }
    }
    int next() {
        int ans = q.front();
        q.pop();
        return ans;
    }

    bool hasNext() {
        return !q.empty();
    }
};

非递归写法

方法差不多,把dfs拆了就是了。

class BSTIterator {
  private:
    queue<int> q;

  public:
    BSTIterator(TreeNode *root) {
        stack<TreeNode *> st;
        TreeNode *p = root;
        while (p || !st.empty()) {
            //优先左走
            if (p) {
                st.push(p);
                p = p->left;
            } else {
                //走不动了,看一下右边
                p = st.top();
                st.pop();
                q.push(p->val);
                p = p->right;
            }
        }
    }

    int next() {
        int ans = q.front();
        q.pop();
        return ans;
    }

    bool hasNext() {
        return !q.empty();
    }
};

标签:BSTIterator,迭代,int,dfs,st,ans,二叉,173
From: https://www.cnblogs.com/CrossAutomaton/p/17867546.html

相关文章

  • 查找 - 二叉排序树/平衡二叉树
    二叉排序树性质:中序遍历是递增的查找算法实现BSTreeSearchBST(BSTreeT,KeyTypekey){if(!T||key==T->data)returnT;elseif(key<T->data)returnSearchBST(T->lchild,key);elsereturnSearchBST(T->rchild,key);}算法分析最坏情况:单支树A......
  • Java集合迭代器的使用
    Java迭代器(Iterator)是Java集合框架中的一种机制,它提供了一种在不暴露集合内部实现的情况下遍历集合元素的方法。JavaIterator(迭代器)不是一个集合,它是一种用于访问集合的方法,可用于迭代ArrayList和HashSet等集合获取迭代器对象Iterator<类型>it=list.iterator();迭代器方......
  • 96. 不同的二叉搜索树(中)
    目录题目动态规划题目动态规划由于1,2...n这个数列是递增的,所以我们从任意一个位置“提起”这课树,都满足二叉搜索树的这个条件:左边儿子数小于爸爸数,右边儿子数大于爸爸数。例如,我要用[1,2,3,4,5,6]构建。首先,提起"2"作为树根,[1]为左子树,[3,4,5,6]为右子树,现在就变成了......
  • python异步迭代器和普通迭代器的区别
    正常迭代器:在Python中,我们可以通过定义__iter__和__next__方法来创建迭代器。在每次调用__next__方法时,迭代器会返回下一个值,直到没有更多的值可以返回,然后它将引发StopIteration异常。这种迭代方式是同步的,意味着每次迭代操作都会等待前一个操作完成。这种方式适合处理大量数据......
  • 13_翻转二叉树
    翻转二叉树给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]【思路】基本思想就是想要翻转二叉树,只需要把每一个节点的左右孩子交......
  • 面试必刷TOP101:34、判断是不是二叉搜索树
    题目题解publicclassSolution{privateTreeNodepre=null;/***给定一个二叉树根节点,请你判断这棵树是不是二叉搜索树***@paramrootTreeNode类*@returnbool布尔型*/publicbooleanisValidBST(TreeNoderoot){......
  • Python实现完全二叉树
    给定一个元素序列(如列表),递归的创建一颗完全二叉树完整代码如下#!/usr/bin/envpython3classTreeNode:"""Nodeofcompletetree"""def__init__(self,data=0):self.data=dataself.left=Noneself.right=Nonedefb......
  • 12_二叉树的最小深度
    二叉树的最小深度给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明:叶子节点是指没有子节点的节点。示例1:输入:root=[3,9,20,null,null,15,7]输出:2示例2:输入:root=[2,null,3,null,4,null,5,null,6]输出:5【思路】当遍......
  • 面试必刷TOP101:33、二叉树的镜像
    题目题解publicTreeNodeMirror(TreeNodepRoot){if(pRoot==null){returnnull;}TreeNoderoot=newTreeNode(pRoot.val);root.left=Mirror(pRoot.right);root.right=Mirror(pRoot.left);retur......
  • 【Python】异步迭代器与普通迭代器的区别
    异步迭代器是一个协程,并且每个迭代器返回一个在asyncio事件循环中调度和执行的等待对象,所以我们可以在迭代器的主体内执行和等待awaitable对象。普通迭代器需要实现__iter__和__next__函数,异步迭代器需要实现__aiter__和__anext__函数。......