二叉树的最近公共祖先并不简单

一、背景

某一天中午吃饭的时候，一同事问我：怎么找二叉树的最近公共祖先。
我起初以为这是一道青铜题，真正了解题意后，发现这是一道王者题。

二、题意

给一棵树，以及树上的两个节点指针。
求这两个节点在树上的最近公共祖先。

如下图，
节点7和节点0的最近公共祖先是节点3。
节点4和节点6的最近公共祖先是节点5。

那该如何实现一个算法，找到两个节点的最近公共祖先呢？

三、链表相交思想

同时问我这个问题的时候，我首先想到的是链表相交，求第一个交点的算法思想。

如果每个节点有指向父节点的指针的话，我们就可以把给的两个节点当做链表头，树的根是链表尾部。
这样问题就转化为了求两个相交链表的第一个交点。

对应的思想是先遍历两个链表分别求出两个链表的长度。
然后对其长度，使得两个节点处于树的同一层。
最后同时向上遍历，判断是不是同一个节点，试了就找到交点了。

但是题目给的是一个普通的二叉树，没有父节点指针，所以就需要想其他方法了。

四、初级递归

面对树的问题，很容易想到递归处理。
同样，这个题也可以使用递归处理。

思路大概是：

1. 先判断公共祖先是否在左子树，是则找到
2. 再判断公共祖先是否在右子树，是则找到
3. 当前根是不是公共祖先，是则找到
4. 当前树没有公共祖先

这里有一个关键问题：怎么判断当前根是不是公共祖先呢？
这个貌似又是一个递归题，可以拆解为根是不是节点A的祖先和根是不是节点B的祖先。
两个同时满足了，根就是这两个节点的公共祖先。

这样这道题我们就做出来了，但是复杂度貌似有点高。
对于每个子树，都进行了判断根是不是祖先，这样就相当于双层循环，复杂度是O(n^2)。

所以我们需要继续思考，有没有更简单的方法。

五、高级递归

其实，在初级递归的时候，复杂度之所高，就是需要在每个子树里判断一个根是不是两个节点的祖先。

这个判断在每个子树里是独立的，但是实际上树与树之间是有关系的。
比如当前树的左儿子是节点A的祖先，那当前树的根肯定也是节点A的祖先。

递归的时候，如果能服用这个信息，则可以将复杂度降低到O(n)。

上面的递归代码需要返回三个值。
最近公共祖先通过返回值返回，没找到则返回NULL。
两个节点是否找到使用参数引用的方式返回。

然后用下面的代码来判断，某个节点是否在当前子树里。

1. 是否等于根
2. 是否在左子树
3. 是否在右子树

pCncestor = p == root || leftPCncestor || rightPCncestor; //if find p in root
qCncestor = q == root || leftQCncestor || rightQCncestor; //if find q in root

这样，这个道题我们就可以在O(N)内解决了。

当然，当时同事网上看的解题源码不是这种思想。
而是一种比较抽象的方法：只有一个返回值，含义是当前子树是否至少含一个节点。

这是一个返回值在不同的条件下含义是不同的。

如下图，如果根和某个节点相同，则返回根。
这里隐含两个含义：

1.如果两个节点都在这颗树里，根是其中一个节点，答案是根。
2.如果只有一个节点在这颗树里，那只能是根了，返回根代表找到了至少一个节点。

然后递归求出连个子树的状态，如果分别都找到一个节点，则代表根是节点。
否则说明这棵树只有一个节点，是谁就返回谁。

六、最后

这道题其实还蛮有难度的，一个递归需要返回多种状态。
状态一多，很多人就弄不明白了。

-EOF-