- 博主简介:努力学习的22级计算机科学与技术本科生一枚🌸
- 博主主页: @是瑶瑶子啦
- 每日一言🌼: 你不能要求一片海洋,没有风暴,那不是海洋,是泥塘——毕淑敏
目录
- 一、题目
- 二、题解
- 三、代码
一、题目
🔗236. 二叉树的最近公共祖先
二、题解
注意:祖先是包括自身的!
-
🍊首先要明白,当root为p,q的最近祖先节点,只有下面3种情况:
1. p,q在root分别存在于root的左右子树中(异侧)——>root即为最近祖先节点
2. p, q均在root的左侧——>p/q即为最近祖先节点
3. p, q均在root的右侧——>同理
-
🍊递归函数的定义
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
:在以root为根节点的树中找并且返回p和q的最近的祖先节点。
1.终止条件:- root == null;return null
root = = p
或者root = = q
,直接返回p/q
2.递推工作:(到这里说明此时p和q要么在此次递归的root的同侧或者异侧)left 用于记录在左侧进行寻找公共祖先(这里的递归函数作用就是单纯找q/p节点并且找到就返回的作用了,当然你可以另外写一个找节点的函数,但是没必要,因为定义的递归函数本身就能实现这个功能),right同理
-
left和right均为null,说明root的左右都没有p,q,那就不存在公共节点,返回Null(有点扯,按理来说,p,q肯定是存在的,但是特判一下也不亏)
-
⭐left和right均不空,说明在此时递归情况是:p,q在
root
异侧,那么直接返回root即可
3. ⭐left不为空,right为空;right不为空,left为空。直接将不为空的那个返回即可!此时不为空的left/right指向的就是最近祖先节点。
三、代码
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q){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){return right;}else if(right == null){return left;}else{return null;}}
💐若有不懂的地方,欢迎随时在评论区or私信找瑶瑶子交流讨论🌺
-
Java岛冒险记【从小白到大佬之路】
-
LeetCode每日一题–进击大厂
-
Go语言核心编程
-
算法