当前位置:网站首页>剑指 Offer 68 - II. 二叉树的最近公共祖先
剑指 Offer 68 - II. 二叉树的最近公共祖先
2022-08-01 04:45:00 【愈努力俞幸运】
考虑通过递归对二叉树进行先序遍历,当遇到节点 p或 q 时返回。从底至顶回溯,当节点 p, q 在节点 root的异侧时,节点 root 即为最近公共祖先,则向上返回 root 。
想上回溯什么?
递归解析:
终止条件:
当越过叶节点,则直接返回 null ;
当 root等于 p,或q,则直接返回 root ;
递推工作:
开启递归左子节点,返回值记为 left ;
开启递归右子节点,返回值记为 right ;
返回值: 根据 left 和 right,可展开为四种情况;
1.当 left 和 right同时为空 :说明 root的左 / 右子树中都不包含 p,q,返回 null ;
2.当 left和 right 同时不为空 :说明 p, q分列在 root的 异侧 (分别在 左 / 右子树),因此 root 为最近公共祖先,返回 root ;
3. 当 left为空 ,right 不为空 :p,q都不在 root的左子树中,直接返回 right。具体可分为两种情况:
(1)p,q其中一个在 root的 右子树 中,假设为p, 此时 right 指向 p;
(2)p,q两节点都在 rootroot 的 右子树 中,此时的 right指向 最近公共祖先节点 ;
4.当 left不为空 , right为空 :与情况 3. 同理;
class Solution:
def lowestCommonAncestor(self, root, p, q):
if not root or root==p or root==q:
return root
left=self.lowestCommonAncestor(root.left,p,q)
right=self.lowestCommonAncestor(root.right, p, q)
if not left and not right:
return
if not left and right:
return right
if not right and left:
return left
return root
边栏推荐
猜你喜欢
leetcode6132. Make all elements in an array equal to zero (simple, weekly)
Typescript22 - interface inheritance
Lawyer Interpretation | Guns or Roses?Talking about Metaverse Interoperability from the Battle of Big Manufacturers
使用ts-node报错
出现Command ‘vim‘ is available in the following places,vim: command not found等解决方法
typescript27-枚举类型呢
Excel做题记录——整数规划优化模型
Typescript20 - interface
【无标题】
Visual Studio提供的 Command Prompt 到底有啥用
随机推荐
Immutable
风险策略调优中重要的三步分析法
动态规划 01背包
Mysql基础篇(约束)
请问表格储存中用sql只能查询到主键列,ots sql非主键不支持吗?
6-23漏洞利用-postgresql代码执行利用
API设计笔记:pimpl技巧
干货!如何使用仪表构造SRv6-TE性能测试环境
怀念故乡的面条
报错:AttributeError: module ‘matplotlib’ has no attribute ‘figure’
[kali-information collection] enumeration - DNS enumeration: DNSenum, fierce
typescript20-接口
【愚公系列】2022年07月 .NET架构班 085-微服务专题 Abp vNext微服务网关
TypeScript simplifies running ts-node
今日睡眠质量记录68分
The kernel's handling of the device tree
李迟2022年7月工作生活总结
基于ProXmoX VE的虚拟化家庭服务器(篇一)—ProXmoX VE 安装及基础配置
【云原生之kubernetes实战】kubernetes集群的检测工具——popeye
Dry goods!How to Construct SRv6-TE Performance Test Environment Using Instrumentation