面试热题（二叉树的最近公共祖先）

ゝ一世哀愁。 2023-10-14 16:24 42阅读 0赞

> 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
> 
> [百度百科][Link 1]中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。”
> 
> 例如，给定如下二叉树: root = \[3,5,1,6,2,0,8,null,null,7,4\]

![d96e58a8be61f77869684deee64964e1.png][]

二叉树的最近公共祖先，这道题无非就是将树进行递归查找

**情况一：当前节点，左树和右树都有分别都有p、q**

![7aeabfd97c724e549e48c39382379295.png][]

**情况二：当前节点，p、q都在其左树上**

![94d27fb909964594a5a7a27c5d67bafb.png][]

**情况三：当前节点，p、q都在其右树上**

![a487832400744fc1a8511206e8b7f9bf.png][]

**情况四：p在q的子树**

![f1de9212d02b4ab2b10b49eb06e1b806.png][]

**情况五：q在p的子树**

![51753c3a9eb8468fa5e3951c2298d13f.png][]

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            //入参进行判断
            if(root==null){
                return null;
            }
            //如果先进来的是p或者q，那肯定是父节点，直接返回
            if(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;
          }
          //两个都在左
          if(left!=null){
           return left;
          }
          //两个都在右边
          if(right!=null){
              return right;
          }
          return null;
        }

[Link 1]: https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin
[d96e58a8be61f77869684deee64964e1.png]: https://img-blog.csdnimg.cn/img_convert/d96e58a8be61f77869684deee64964e1.png
[7aeabfd97c724e549e48c39382379295.png]: https://img-blog.csdnimg.cn/7aeabfd97c724e549e48c39382379295.png
[94d27fb909964594a5a7a27c5d67bafb.png]: https://img-blog.csdnimg.cn/94d27fb909964594a5a7a27c5d67bafb.png
[a487832400744fc1a8511206e8b7f9bf.png]: https://img-blog.csdnimg.cn/a487832400744fc1a8511206e8b7f9bf.png
[f1de9212d02b4ab2b10b49eb06e1b806.png]: https://img-blog.csdnimg.cn/f1de9212d02b4ab2b10b49eb06e1b806.png
[51753c3a9eb8468fa5e3951c2298d13f.png]: https://img-blog.csdnimg.cn/51753c3a9eb8468fa5e3951c2298d13f.png