江阴网站制作设计,搭建自己的个人网站,手游传奇新开服网站,wordpress管理员手册博主简介#xff1a;努力学习的22级计算机科学与技术本科生一枚#x1f338;博主主页#xff1a; 是瑶瑶子啦每日一言#x1f33c;: 你不能要求一片海洋#xff0c;没有风暴#xff0c;那不是海洋#xff0c;是泥塘——毕淑敏 目录 一、题目二、题解三、代码 一、题目
… 博主简介努力学习的22级计算机科学与技术本科生一枚博主主页 是瑶瑶子啦每日一言: 你不能要求一片海洋没有风暴那不是海洋是泥塘——毕淑敏 目录 一、题目二、题解三、代码 一、题目
236. 二叉树的最近公共祖先 二、题解 注意祖先是包括自身的 首先要明白当root为p,q的最近祖先节点只有下面3种情况 1. pq在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 nullreturn nullroot 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语言核心编程 算法
