[剑指offer]面试题第[68-2]题[Leetcode][第236题][JAVA][二叉搜索树的最近公共祖先][递归]

怼烎@ 2023-02-26 15:27 42阅读 0赞

#### 【问题描述】\[中等\] ####

**235/68-1 搜索二叉树 236/68-2 二叉树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]

###### 递归 ######

**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200716112354761.png]

**情况 1. , 2. , 3. , 4. 的展开写法如下。**

class Solution { 
        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 null; // 1.
            if(left == null) return right; // 3.
            if(right == null) return left; // 4.
            return root; // 2. if(left != null and right != null)
        }
    }

**优化版**

class Solution { 
        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) return right;
            if(right == null) return left;
            return root;
        }
    }

**注释版**

//方法二：后序遍历，先左子树后右子树最后root,从底至顶回溯，代码简单，但是分析起来复杂;
        //当root==null时，说明当前路径没有找到p或者q
        //当root==p||root==q,假设先找到的是节点p:
        //则继续从找到的节点p开始寻找另一个节点q(迭代)，当第二个节点q也找到时,进行回溯,一开始回溯时，会一直保持单侧子树不为null的情况，但是注意这种情况，不是由于p,q均在当前单侧子树造成的，当前回溯过程的单侧子树内只有一个q;
        //继续回溯，当回溯至一个节点root时,节点 p,q在节点root的异侧,即双侧子树均不为null时,节点 root即为最近公共祖先。
        //返回root，后续则又会变为单侧子树不为null,这时才是因为p,q均在当前单侧子树造成的;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            //root=null,返回root说明这条路径没有找到p或者q;root=p||root=q时说明当前找到了p或者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语句可以交换顺序，如果固定顺序，则后面两个if可以进行简化
            //当root的左子树和右子树都没有p或者q时，root不是p和q祖先,返回null;
            if(left==null&&right==null) return null;
            
            //基于第一个if，这里的if可以简写为if(right==null) return left;
            //这里root的右子树没有找到p或者q,left找到了p或者q,这里返回的left有两种情况：
            //1.未找到最近公共节点时，即还在迭代阶段，这里返回的left为找到的p(假设为p),即第一个if的return结果：
            //若前面没有找到q,则从p开始继续进行迭代,在二叉树中剩余的节点中找到剩下的那个q; 若之前已经找到了q，则开始返回，直到找到left!=null&&right!=null，即找到了最近公共祖宗；
            //2.找到最近公共节点时，即处于返回阶段,不需要再进行迭代了,此时p,q在同一侧子树中,这里left为找到的最近公共节点,即下面最后一个return的结果;
            if(left!=null&&right==null) return left;
            //基于第一个if，这里的if可以简写为if(left==null) return right;
            //这里的分析和上面一个if类似;
            if(left==null&&right!=null) return right;
            return root;//即if(left!=null&&right!=null) return root;但注释中的写法会使得函数缺少return语句;
        }

#### 【总结】 ####

###### 1. 二叉树遍历 ######

前序遍历 先输出当前结点的数据，再依次遍历输出左结点和右结点  
中序遍历 先遍历输出左结点，再输出当前结点的数据，再遍历输出右结点  
后续遍历 先遍历输出左结点，再遍历输出右结点，最后输出当前结点的数据

###### 2. 对于二叉树的题，开始可以用递归的思想去思考单 代码简单 过程不简单 ######

###### 3. 相关题目[\[剑指offer\]面试题第\[68-1\]题\[Leedcode\]][offer_68-1_Leedcode]\[JAVA\]\[第235题\]\[二叉搜索树的最近公共祖先\]\[递归\]\[BFS\] ######

作者：Krahets  
转载链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-er-cha-shu-de-zui-jin-gong-gon-7/

参考链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-javashi-xian-jian-zhi-offersi-lu/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/29c0bad8d75d475f991ffbdc5dc9af83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200716112254407.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200716112323357.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200716112532295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200716112541849.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200716112603286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200716112354761.png]: https://img-blog.csdnimg.cn/20200716112354761.png
[offer_68-1_Leedcode]: https://blog.csdn.net/dadongwudi/article/details/106037304