如何找出一个二叉树中任意两个节点的最低公共祖先？

深藏阁楼爱情的钟 2023-09-27 18:29 114阅读 0赞

## 前言 ##

本文将介绍如何找出一个二叉树中任意两个节点的最低公共祖先。

## 正文 ##

题目描述如下：

给出一棵二叉树的头结点`head`和另外两个`节点a`和`节点b`，返回`节点a`和`节点b`的最低公共祖先。

最低公共祖先是指最接近`节点a`和`节点b`的公共上级节点。

如下图中，`节点8`和`节点9`的公共祖先有`节点7`和`节点5`，`节点7`距离`节点8`和`节点9`最近，所以`节点7`为`节点8`和`节点9`的最低公共祖先。

注意：`节点a`或`节点b`也可能是`节点a`和`节点b`的最低公共祖先。

![format_png][]

### 思路分析 ###

有一个简单的方法来实现就是在遍历的时候，把每个节点的父节点给记录下来，比如放到一个`Map`中，在查找两个节点的最低父节点时，从`Map`中递归查找一下，如果两个节点能找到公共的节点，那么这个公共节点就是最低公共祖先。

根据之前介绍的二叉树递归套路的话，这道题其实也是可以用二叉树递归套路来实现的。递归套路需要一个每次递归都返回同样的信息，先来看下这道题的递归信息是什么。

这道题的递归信息是节点汇聚的目标，两个节点向上汇聚，如果有交叉则返回交叉的节点，如果没有交叉则返回`null`。

如果有交叉，说明这棵树上可定有这两个节点的存在。

对于一个节点存在两种情况：

*  该节点不是最低汇聚点
 *  该节点是最低汇聚点

针对这两种情况进行分析，在什么情况下该节点不是最低汇聚点？

*  该节点的左树上已经有最低汇聚点
 *  该节点的右树上已经有最低汇聚点
 *  该节点所在的子树没有同时找到两个给出的节点

在什么情况下该节点是最低汇聚点？

*  该节点的左树和右树分别发现了给出的两个节点
 *  该节点本身就是给出的一个节点，在该节点的左树或右树存在两一个节点

所以，递归所需要的信息有：

*  这棵二叉树上存不存在`节点a`
 *  这棵二叉树上存不存在`节点b`
 *  这棵二叉树上存不存在最低公共祖先

### 代码实现 ###

根据上面的思路分析，来看一下代码实现，首先看下信息类的定义：

public class Info {
       public boolean findA;
       public boolean findB;
       public Node ans;
    
       public Info(boolean findA, boolean findB, Node ans) {
          this.findA = findA;
          this.findB = findB;
          this.ans = ans;
       }
    }
    复制代码

再看下递归函数的代码实现：

public Info process(Node x, Node a, Node b) {
       if (x == null) {
          return new Info(false, false, null);
       }
       Info leftInfo = process(x.left, a, b);
       Info rightInfo = process(x.right, a, b);
       // x是不是a，左树有没有a，右树有没有a
       boolean findA = (x == a) || leftInfo.findA || rightInfo.findA;
       // x是不是b，左树有没有b，右树有没有b
       boolean findB = (x == b) || leftInfo.findB || rightInfo.findB;
       Node ans = null;
       if (leftInfo.ans != null) {
          // 左树上有最低公共祖先
          ans = leftInfo.ans;
       } else if (rightInfo.ans != null) {
          // 右树上有最低公共祖先
          ans = rightInfo.ans;
       } else {
          if (findA && findB) {
             // 如果即发现了a、又发现了b，那么x就是最低公共祖先
             ans = x;
          }
       }
       // 返回封装信息
       return new Info(findA, findB, ans);
    }
    复制代码

主函数调用，代码如下：

public Node lowestAncestor(Node head, Node a, Node b) {
       return process(head, a, b).ans;
    }
    复制代码

## 总结 ##

本文将介绍如何找出一个二叉树中任意两个节点的最低公共祖先，文中使用了二叉树递归的套路解决了这道题，另外还可以使用`Map`来暴力递归方式实现，这里接不再介绍了，有兴趣的小伙伴可以自己试试~

[format_png]: https://img-blog.csdnimg.cn/img_convert/bae49764db4a0bfd6dd61715ea0e4246.webp?x-oss-process=image/format,png