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

一、背景

某一天中午吃饭的时候，一同事问我：怎么找二叉树的最近公共祖先。

我起初以为这是一道青铜题，真正了解题意后，发现这是一道王者题。

二、题意

给一棵树，以及树上的两个节点指针。

求这两个节点在树上的最近公共祖先。

如下图，

节点 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-