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

前言

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

正文

题目描述如下：

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

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

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

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

思路分析

有一个简单的方法来实现就是在遍历的时候，把每个节点的父节点给记录下来，比如放到一个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来暴力递归方式实现，这里接不再介绍了，有兴趣的小伙伴可以自己试试~