二叉树的最近公共祖先：超清晰图解和详解

二叉树的最近公共祖先：超清晰图解和详解

引用

CSDN

1.

https://blog.csdn.net/Yaoyao2024/article/details/132278792

一、题目

236. 二叉树的最近公共祖先

二、题解

注意：祖先是包括自身！

🍊首先要明白，当root为p,q的最近祖先节点（这里假设root不包含pq自身，方便我们分析），只有下面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同理

1. left和right均为null，说明root的左右都没有p,q，那就不存在公共节点，返回Null（有点扯，按理来说，p,q肯定是存在的，但是特判一下也不亏）
2. ⭐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;
    }
}