C++实现LeetCode(173.二叉搜索树迭代器)
[LeetCode] 173.Binary Search Tree Iterator 二叉搜索树迭代器
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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
这道题主要就是考二叉树的中序遍历的非递归形式,需要额外定义一个栈来辅助,二叉搜索树的建树规则就是左<根<右,用中序遍历即可从小到大取出所有节点。代码如下:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class BSTIterator { public: BSTIterator(TreeNode *root) { while (root) { s.push(root); root = root->left; } } /** @return whether we have a next smallest number */ bool hasNext() { return !s.empty(); } /** @return the next smallest number */ int next() { TreeNode *n = s.top(); s.pop(); int res = n->val; if (n->right) { n = n->right; while (n) { s.push(n); n = n->left; } } return res; } private: stack<TreeNode*> s; }; /** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */
相关推荐
-
C++实现LeetCode(169.求大多数)
[LeetCode] 169. Majority Element 求大多数 Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1
-
C++实现LeetCode(167.两数之和之二 - 输入数组有序)
[LeetCode] 167.Two Sum II - Input array is sorted 两数之和之二 - 输入数组有序 Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of t
-
C++实现LeetCode165.版本比较)
[LeetCode] 165.Compare Version Numbers 版本比较 Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 <version2 return -1;otherwise return 0. You may assume that the version strings are non-empty and contain onl
-
C++实现LeetCode(171.求Excel表列序号)
[LeetCode] 171.Excel Sheet Column Number 求Excel表列序号 Related to question Excel Sheet Column Title Given a column title as appear in an Excel sheet, return its corresponding column number. For example: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -&g
-
C++实现LeetCode(170.两数之和之三 - 数据结构设计)
[LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai
-
C++实现LeetCode(166.分数转循环小数)
[LeetCode] 166.Fraction to Recurring Decimal 分数转循环小数 Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses. Fo
-
C++实现LeetCode(168.求Excel表列名称)
[LeetCode] 168.Excel Sheet Column Title 求Excel表列名称 Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example: 1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ... Example 1: Input: 1 O
-
C++实现LeetCode(172.求阶乘末尾零的个数)
[LeetCode] 172. Factorial Trailing Zeroes 求阶乘末尾零的个数 Given an integer n, return the number of trailing zeroes in n!. Example 1: Input: 3 Output: 0 Explanation: 3! = 6, no trailing zero. Example 2: Input: 5 Output: 1 Explanation: 5! = 120, one trailing
-
C++实现LeetCode(173.二叉搜索树迭代器)
[LeetCode] 173.Binary Search Tree Iterator 二叉搜索树迭代器 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
-
C++实现LeetCode(96.独一无二的二叉搜索树)
[LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树 Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3
-
C++实现LeetCode(95.独一无二的二叉搜索树之二)
[LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二 Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3],
-
C++实现LeetCode(99.复原二叉搜索树)
[LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2] 1 / 3 \ 2 Output: [3,1,null,null,2] 3 / 1
-
C++实现LeetCode(98.验证二叉搜索树)
[LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The ri
-
C++实现LeetCode(109.将有序链表转为二叉搜索树)
[LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary
-
C++实现LeetCode(108.将有序数组转为二叉搜索树)
[LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh
-
Java数据结构之二叉搜索树详解
目录 前言 性质 实现 节点结构 初始化 插入节点 查找节点 删除节点 最后 前言 今天leetcode的每日一题450是关于删除二叉搜索树节点的,题目要求删除指定值的节点,并且需要保证二叉搜索树性质不变,做完之后,我觉得这道题将二叉搜索树特性凸显的很好,首先需要查找指定节点,然后删除节点并且保持二叉搜索树性质不变,就想利用这个题目讲讲二叉搜索树. 二叉搜索树作为一个经典的数据结构,具有链表的快速插入与删除的特点,同时查询效率也很优秀,所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数
-
Java动态规划方式解决不同的二叉搜索树
目录 一.题目描述 二.思路 三.代码 一.题目描述 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数. 来源:https://leetcode.cn/problems/unique-binary-search-trees/ 二.思路 本题可以使用动态规划的方式解决,我们先来看一下大题思路.以 n = 3 为例,n = 3 时的不同的二叉搜索树数目,可以通过分别 以 1 为根节点,以 2 为根节点,以 3 为根节点
-
Javascript实现从小到大的数组转换成二叉搜索树
废话不多说了,直接给大家贴代码了,具体代码如下所示: var Array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; var Tree = createTree(Array); console.log(Tree); // 构造一个节点 function Node(nodeData, leftData, rightData) { this.nodeData = nodeData; this.leftData = leftData; this.rightData = rig
随机推荐
- 《CSS3实战》笔记--渐变设计(三)
- Python数据结构与算法之图结构(Graph)实例分析
- asp.net批量多选文件上传解决方案
- PHP5下$_SERVER变量不再受magic_quotes_gpc保护的弥补方法
- PHP大转盘中奖概率算法实例
- ASP网站生成静态html页面技术小结
- 浅谈C#单例模式的实现和性能对比
- Android中的序列化浅析
- mysql动态游标学习(mysql存储过程游标)
- BootStrap智能表单实战系列(八)表单配置json详解
- 070823更新的一个[消息提示框]组件 兼容ie7
- 多用多学之Java中的Set,List,Map详解
- C#实现缩放和剪裁图片的方法示例
- 快速理解Java设计模式中的组合模式
- python3爬取淘宝信息代码分析
- mpvue全局引入sass文件的方法步骤
- python模糊图片过滤的方法
- vue+高德地图写地图选址组件的方法
- Laravel框架实现的批量删除功能示例
- C++中map和vector作形参时如何给定默认参数?