当前位置:网站首页>leetcode 二叉树的公共近祖先
leetcode 二叉树的公共近祖先
2022-08-09 18:52:00 【老鱼37】
思路:
遇到这个题目首先想的是要是能自底向上查找就好了,这样就可以找到公共祖先了。
那么二叉树如何可以自底向上查找呢?
回溯啊,二叉树回溯的过程就是从低到上。
后序遍历就是天然的回溯过程,最先处理的一定是叶子节点。
接下来就看如何判断一个节点是节点q和节点p的公共公共祖先呢。
如果找到一个节点,发现左子树出现结点p,右子树出现节点q,或者 左子树出现结点q,右子树出现节点p,那么该节点就是节点p和q的最近公共祖先。
使用后序遍历,回溯的过程,就是从低向上遍历节点,一旦发现如何这个条件的节点,就是最近公共节点了。
递归三部曲:
1.确定递归函数的返回值及其参数
2.确定递归终止条件
3.确定单层递归的逻辑
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(q==root||p==root||root==NULL) return root;
TreeNode*left=lowestCommonAncestor(root->left,p,q);//遍历左子树
TreeNode*right=lowestCommonAncestor(root->right,p,q);//遍历右子树
if(left!=NULL&&right!=NULL) return root;
else if(left!=NULL&&right==NULL) return left;
else if(right!=NULL&&left==NULL) return right;
else
{
return NULL;
}
}
};
总结:
1.求最小公共祖先,需要从底向上遍历,那么二叉树,只能通过后序遍历(即:回溯)实现从底向上的遍历方式。
2.在回溯的过程中,必然要遍历整颗二叉树,即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断。
3.要理解如果返回值left为空,right不为空为什么要返回right,为什么可以用返回right传给上一层结果。
如有错误,多多指教!
边栏推荐
- 2021 RoboCom 世界机器人开发者大赛-本科组(决赛)
- 渗透测试——CFS三层靶机内网渗透实操
- 小满nestjs(第四章 前置知识装饰器-实现一个GET请求)
- MYSQL记录、自用
- MFC tutorial
- 2022深圳(软考中级)系统集成项目管理工程师报名
- 开源一夏 | 基于若依架构的列表详情展示
- [免费专栏] Android安全之Android应用的汉化功能(修改so中的字符串内容)
- 启动 CM agent 报错——ImportError: libssl.so.10: cannot open shared object file: No such file or directory
- ebook下载 | 《 企业高管IT战略指南——企业为何要落地DevOps》
猜你喜欢
随机推荐
典型的数据仓库模型实施过程详解
mysql duplicate data group multiple latest records
基于SSM实现手机销售商城系统
大健康产业商业供应链管理系统数字化提升产业链运作效率推动供应链标准化建设
环境:Flink版本:1.15.1jar包:flink-sql-connector-oracle
[免费专栏] Android安全之ZIP文件目录遍历漏洞
时序攻击
源码编译安装与yum和rpm软件安装详解
2021 RoboCom 世界机器人开发者大赛-本科组(决赛)
『百日百题 · 基础篇』备战面试,坚持刷题 第五话——循环语句(2)!
2022.08.06_每日一题
21天学习挑战赛--第四天打卡(横竖屏切换)
超多AI开发者等你来玩转,一起燃动昇腾AI创享日南京站!
[免费专栏] Android安全之Android应用的汉化功能(修改so中的字符串内容)
有文章说明或者证明MYSQL 嵌套子查询不足之处吗?
C#/VB.NET:从PowerPoint文档中提取文本和图片
hdu 2647 Reward(拓扑排序)
数学建模——模拟退火
Start cleaning up the long-term divers in the electronic chart development group again
华为云全流程护航《流浪方舟》破竹首发,打造口碑爆款