当前位置:网站首页>Lc173. Binary search tree iterator
Lc173. Binary search tree iterator
2022-07-02 22:59:00 【996 Chong Chong】
In fact, it is equivalent to the middle order traversal of binary search tree , stay next Return a result when .
So you can directly store all the results of the middle order traversal in the call next Method # Method 1
class BSTIterator(object):
def __init__(self, root):
""" :type root: TreeNode """
self.queue = collections.deque()
self.inorder(root)
def inorder(self,root):
if not root:
return
self.inorder(root.left)
self.queue.append(root.val)
self.inorder(root.right)
def next(self):
""" :rtype: int """
return self.queue.popleft()
def hasNext(self):
""" :rtype: bool """
return len(self.queue) > 0
You can also use the iterative method to traverse the middle order , Split the iterative method into next Back in # Method 2
class BSTIterator(object):
def __init__(self, root):
""" :type root: TreeNode """
self.stack =[]
while root:
self.stack.append(root)
root = root.left
def next(self):
""" :rtype: int """
cur = self.stack.pop()
node = cur.right
while node:
self.stack.append(node)
node = node.left
return cur.val
def hasNext(self):
""" :rtype: bool """
return len(self.stack)>0
边栏推荐
- What is the'function'keyword used in some bash scripts- What is the 'function' keyword used in some bash scripts?
- 【板栗糖GIS】global mapper 如何通过dsm批量制作贴地等高线
- JS syntax ES6, ES7, es8, es9, ES10, es11, ES12 new features (Abstract)
- AES高級加密協議的動機闡述
- Storage unit conversion
- The threshold value of fusing proportion cannot be changed with sentinel, and setting the slow call proportion has no effect
- 高并发介绍及应对
- `Usage of ${}`
- Addition, deletion, modification and query of handwritten ORM (object relationship mapping)
- 【板栗糖GIS】arcmap—为什么使用自定义捕捉的时候,经典捕捉的勾要去掉呢?
猜你喜欢
Xiaopeng P7 had an accident and the airbag did not pop up. Is this normal?
[Solved] Splunk: Cannot get username when all users are selected“
Dahua cloud native load balancing article - the passenger flow of small restaurants has increased
Local dealers play the community group purchase mode and share millions of operations
AES高級加密協議的動機闡述
中国信通院、清华大学、腾讯安全,云原生安全产学研用强强联合!
PMP project integration management
`${}`的用法
Jatpack------LiveData
PMP项目整合管理
随机推荐
Chow-Liu Tree
Zhong Xuegao responded that the product will not melt for 1 hour: it contains solid components and cannot melt into water
The kth largest element in the [leetcode] array [215]
杰理之如何测试按键的误触率【篇】
[chestnut sugar GIS] ArcScene - how to make elevation map with height
悬镜安全在RSAC2022上斩获Global InfoSec Awards四项大奖
世界环境日 | 周大福用心服务推动减碳环保
大一学习分享
从2022年Q1财报看携程的韧性和远景
Array advanced improvement
解决Chrome浏览器和Edeg浏览器主页被篡改的方法
Jerry's prototype will trigger shutdown after multiple touches [chapter]
WebRTC音视频采集和播放示例及MediaStream媒体流解析
Learning records of data analysis (II) -- simple use of response surface method and design expert
P1007 独木桥
`${}`的用法
【洛谷P1541】乌龟棋【DP】
DTM distributed transaction manager PHP collaboration client V0.1 beta release!!!
电商系统微服务架构
Jatpack------LiveData