leetcood学习笔记-235-二叉搜索树的最近公共祖先
2024-10-07 16:24:25
题目描述：
利用二叉搜索树的特点，如果p、q的值都小于root，说明p q 肯定在root的左子树中；如果p q都大于root，说明肯定在root的右子树中，如果一个在左一个在右 则说明此时的root记为对应的最近公共祖先
方法一：递归
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if max(p.val,q.val) < root.val:
return self.lowestCommonAncestor(root.left,p,q)
if min(p.val,q.val) > root.val:
return self.lowestCommonAncestor(root.right,p,q)
return root
方法二：迭代
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if max(p.val,q.val) < root.val:
root = root.left
elif min(p.val,q.val) > root.val:
root = root.right
else:
return root
最新文章
- css声明应用优先级
- 如何利用cookie来保存用户登录账号
- 数据仓库原理<1>：数据库与数据仓库
- ACM入门记
- 如何用C表示排列组合？
- easy ui 表单元素input控件后面加说明（红色）
- Android 电子邮件发送成功与失败的提示
- SQL Prompt5 破解版+使用说明 [转]
- 通过 Visual Studio 的“代码度量值”来改进代码质量
- 小项目：聊天室 （jQuery，PHP，MySQL）
- iOS开发出错whose view is not in the window hierarchy!的解决
- 安装ubuntu18.10并连接xshell6
- 监控服务器配置(四)-----OracleDb_exporter安装配置
- POI导出Execl文件,使JAVA虚拟机OOM
- 最强Hibernate搭建文章（转）
- C# event关键字
- flask框架----数据库连接池
- NSIS笔记
- shell 命令 netstat 查看端口占用
- STL——迭代器与traits编程技法