leetcode 173. Binary Search Tree Iterator

红太狼 2022-07-26 00:25 136阅读 0赞

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling `next()` will return the next smallest number in the BST.

Note: `next()` and `hasNext()` should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

class BSTIterator {
    	vector<int>re;
    	int k;
    public:
    	BSTIterator(TreeNode *root) {
    		if (root == NULL)
    			return ;
    		vector<TreeNode*>que;
    		que.push_back(root);
    		bool f = true;
    		while (!que.empty())
    		{
    			if (f&&que.back()->left != NULL)
    				que.push_back(que.back()->left);
    			else
    			{
    				re.push_back(que.back()->val);
    				TreeNode*n = que.back(); que.pop_back();
    				if (n->right != NULL)
    				{
    					que.push_back(n->right);
    					f = true;
    				}
    				else
    					f = false;
    			}
    		}
    		k = 0;
    	}
    
    	/** @return whether we have a next smallest number */
    	bool hasNext() {
    		return re.size() > k;
    	}
    
    	/** @return the next smallest number */
    	int next() {
    		return re[k++];
    	}
    };

accepted

发表评论取消回复

表情：

评论列表（有 0 条评论，136人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 173. Binary Search Tree Iterator

Topic Stack Tree Design Description [https://leetcode.com/problems/binar

超、凢脫俗/ 2022年10月16日 15:20/ 0 赞/ 156 阅读

相关 Recover Binary Search Tree--LeetCode

题目：Two elements of a binary search tree (BST) are swapped by mistake.Recover the tree wi

喜欢ヅ旅行/ 2022年08月05日 14:23/ 0 赞/ 168 阅读

相关 Unique Binary Search Trees--LeetCode

题目： Given n, how many structurally unique BST's (binary search trees) that store valu

ゞ浴缸里的玫瑰/ 2022年08月05日 14:18/ 0 赞/ 156 阅读

相关 leetcode Binary Search Tree Iterator

题目原题链接：[https://leetcode.com/problems/binary-search-tree-iterator/][https_leetcode.c

素颜马尾好姑娘i/ 2022年08月04日 16:58/ 0 赞/ 170 阅读

相关 LeetCode173-Binary Search Tree Iterator

LeetCode 173 : Binary Search Tree Iterator Implement an iterator over a binary search t

女爷i/ 2022年08月04日 12:48/ 0 赞/ 5 阅读

相关 leetcode 173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized

红太狼/ 2022年07月26日 00:25/ 0 赞/ 137 阅读

相关 LeetCode173—Binary Search Tree Iterator

原题 [原题链接][Link 1] > Implement an iterator over a binary search tree (BST). Your iter

骑猪看日落/ 2022年07月14日 06:26/ 0 赞/ 148 阅读

相关 leetcode 173. Binary Search Tree Iterator 二叉树中序遍历非递归

Implement an iterator over a binary search tree (BST). Your iterator will be initialized

阳光穿透心脏的1/2处/ 2022年06月08日 08:18/ 0 赞/ 157 阅读

相关 LeetCode 173.Binary Search Tree Iterator (二叉搜索树迭代器)

题目描述：实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用 `next()` 将返回二叉搜索树中的下一个最小的数。注意:`next()` 和`

àì夳堔傛蜴生んèń/ 2022年04月15日 00:21/ 0 赞/ 157 阅读

相关 [Leetcode] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree wit

淡淡的烟草味﹌/ 2021年12月03日 07:25/ 0 赞/ 181 阅读