当前位置:网站首页>Lc669. Prune binary search tree
Lc669. Prune binary search tree
2022-07-01 22:39:00 【996 Chong Chong】
iteration
def trimBST(self, root, low, high):
""" :type root: TreeNode :type low: int :type high: int :rtype: TreeNode """
if not root:
return
while root and (root.val < low or root.val > high): # Find the legal root
if root.val < low:
root = root.right
elif root.val > high:
root = root.left
cur = root
while cur:
while cur.left and cur.left.val < low: # Find the unqualified one on the left
cur.left = cur.left.right # After finding it, all the left subtree can be discarded , And connect the right subtree of the unqualified node to cur On
cur = cur.left # Keep looking ( According to the characteristics of binary tree, if you don't find it, keep looking to the left )
cur = root
while cur:
while cur.right and cur.right.val > high: # Find the unqualified one on the right
cur.right = cur.right.left # After finding the right subtree, all can be discarded , And connect the left subtree of the unqualified node to cur On
cur = cur.right # Keep looking ( According to the characteristics of binary tree, if you don't find it, keep looking to the right )
return root
recursive
def trimBST(self, root, low, high): # Trim from the root node
""" :type root: TreeNode :type low: int :type high: int :rtype: TreeNode """
if not root:
return
if root.val < low:
return self.trimBST(root.right,low,high) # Here is for pruning , And finally return the pruned result ( Is to run recursive statements first , Finally, when you return to the current statement , Will execute return)
# Equivalent to
# left = self.trimBST(root.right,low,high) # First perform recursion , The following sentence will be executed only when you return to this sentence
# return left
elif root.val > high:
return self.trimBST(root.left,low,high)
root.left = self.trimBST(root.left,low,high) # If the root node is ok , Then recursively prune the left and right child nodes
root.right = self.trimBST(root.right,low,high)
return root
recursive , Equivalent to bottom-up construction , First finish all the pruning , after return root Connect slowly , Finally, connect the pruned left and right subtrees .
def trimBST(self, root, low, high):
""" :type root: TreeNode :type low: int :type high: int :rtype: TreeNode """
if not root:
return
if root.val >= low: # Prune the left and right child nodes normally
root.left = self.trimBST(root.left,low,high)
else: # If the root node is too small , And its left subtree is smaller than it, so just return to the pruning result of the right subtree
return self.trimBST(root.right,low,high)
if root.val <= high:
root.right = self.trimBST(root.right,low,high)
else: # If the root node is too large , And its right subtree is larger than it, so just return to the pruning result of the left subtree
return self.trimBST(root.left,low,high)
return root
边栏推荐
- 分享一个一年经历两次裁员的程序员的一些感触
- Rust语言——小小白的入门学习05
- C#/VB.NET 给PDF文档添加文本/图像水印
- LIS (longest ascending subsequence) problem that can be understood [easy to understand]
- Recent public ancestor offline practice (tarjan)
- GenICam GenTL 标准 ver1.5(4)第五章 采集引擎
- Getting started with the lockust series
- 100年仅6款产品获批,疫苗竞争背后的“佐剂”江湖
- MySQL之MHA高可用配置及故障切换
- MySQL MHA high availability configuration and failover
猜你喜欢
[intelligent QBD risk assessment tool] Shanghai daoning brings you leanqbd introduction, trial and tutorial
MySQL learning notes - SQL optimization of optimization
Redis configuration and optimization
首席信息官对高绩效IT团队定义的探讨和分析
园区全光技术选型-中篇
【MySQL】索引的分类
# CutefishOS系统~
Kubernetes创建Service访问Pod
小 P 周刊 Vol.11
EasyExcel 复杂数据导出
随机推荐
[jetcache] how to use jetcache
linux下清理系统缓存并释放内存
Wechat open platform scanning code login [easy to understand]
Redis配置与优化
小 P 周刊 Vol.11
Matlab traverses images, string arrays and other basic operations
Kubernetes创建Service访问Pod
Rust语言——小小白的入门学习05
YOLOv5.5 调用本地摄像头
The difference between NiO and traditional IO
切面条 C语言
JVM有哪些类加载机制?
Slope compensation
并发编程系列之FutureTask源码学习笔记
Classify boost libraries by function
20220701
The correct way to set the bypass route
[STM32] stm32cubemx tutorial II - basic use (new projects light up LED lights)
微信开放平台扫码登录[通俗易懂]
A debugging to understand the slot mechanism of redis cluster