【算法思想·二叉树】最近公共祖先问题

本文参考labuladong算法笔记[拓展：最近公共祖先系列解题框架 | labuladong 的算法笔记]

0、引言

如果说笔试的时候经常遇到各种动归回溯这类稍有难度的题目，那么面试会倾向于一些比较经典的问题，难度不算大，而且也比较实用。

本文就用 Git 引出一个经典的算法问题：最近公共祖先（Lowest Common Ancestor），简称 LCA。

git pull 这个命令我们经常会用，它默认是使用 merge 方式将远端别人的修改拉到本地；如果带上参数 git pull -r，就会使用 rebase 的方式将远端修改拉到本地。

这二者最直观的区别就是：merge 方式合并的分支会看到很多「分叉」，而 rebase 方式合并的分支就是一条直线。但无论哪种方式，如果存在冲突，Git 都会检测出来并让你手动解决冲突。

那么问题来了，Git 是如何检测两条分支是否存在冲突的呢？

以 rebase 命令为例，比如下图的情况，我站在 dev 分支执行 git rebase master，然后 dev 就会接到 master 分支之上：

这个过程中，Git 是这么做的：

首先，找到这两条分支的最近公共祖先 LCA，然后从 master 节点开始，重演 LCA 到 dev 几个 commit 的修改，如果这些修改和 LCA 到 master 的 commit 有冲突，就会提示你手动解决冲突，最后的结果就是把 dev 的分支完全接到 master 上面。

那么，Git 是如何找到两条不同分支的最近公共祖先的呢？这就是一个经典的算法问题了，下面我来由浅入深讲一讲。

1、寻找一个元素

先不管最近公共祖先问题，我请你实现一个简单的算法：

给你输入一棵没有重复元素的二叉树根节点 root 和一个目标值 val，请你写一个函数寻找树中值为 val 的节点。

函数签名如下：

def find(root: TreeNode, val: int) -> TreeNode:

这个函数应该很容易实现对吧，比如我这样写代码：

# 定义：在以 root 为根的二叉树中寻找值为 val 的节点
def find(root: TreeNode, val: int) -> TreeNode:# base caseif not root:return None# 看看 root.val 是不是要找的if root.val == val:return root# root 不是目标节点，那就去左子树找left = find(root.left, val)if left:return left# 左子树找不着，那就去右子树找right = find(root.right, val)if right:return right# 实在找不到了return None

这段代码应该不用我多解释了，我下面基于这段代码做一些简单的改写，请你分析一下我的改动会造成什么影响。

首先，我修改一下 return 的位置：

def find(root: TreeNode, val: int) -> TreeNode:if not root:return None# 前序位置if root.val == val:return root# root 不是目标节点，去左右子树寻找left = find(root.left, val)right = find(root.right, val)# 看看哪边找到了return left if left else right

这段代码也可以达到目的，但是实际运行的效率会低一些，原因也很简单，如果你能够在左子树找到目标节点，还有没有必要去右子树找了？没有必要。但这段代码还是会去右子树找一圈，所以效率相对差一些。

更进一步，我把对 root.val 的判断从前序位置移动到后序位置：

def find(root: TreeNode, val: int) -> TreeNode:if root is None:return None# 先去左右子树寻找left = find(root.left, val)right = find(root.right, val)# 后序位置，看看 root 是不是目标节点if root.val == val:return root# root 不是目标节点，再去看看哪边的子树找到了return left if left is not None else right

这段代码相当于你先去左右子树找，然后才检查 root，依然可以到达目的，但是效率会进一步下降。因为这种写法必然会遍历二叉树的每一个节点。

对于之前的解法，你在前序位置就检查 root，如果输入的二叉树根节点的值恰好就是目标值 val，那么函数直接结束了，其他的节点根本不用搜索。

但如果你在后序位置判断，那么就算根节点就是目标节点，你也要去左右子树遍历完所有节点才能判断出来。

最后，我再改一下题目，现在不让你找值为 val 的节点，而是寻找值为 val1 或 val2 的节点，函数签名如下：

def find(root: TreeNode, val1: int, val2: int) -> TreeNode:

这和我们第一次实现的 find 函数基本上是一样的，而且你应该知道可以有多种写法，我选择这样写代码：

# 定义：在以 root 为根的二叉树中寻找值为 val1 或 val2 的节点
def find(root, val1, val2):# base caseif root is None:return None# 前序位置，看看 root 是不是目标值if root.val == val1 or root.val == val2:return root# 去左右子树寻找left = find(root.left, val1, val2)right = find(root.right, val1, val2)# 后序位置，已经知道左右子树是否存在目标值return left if left is not None else right

为什么要写这样一个奇怪的 find 函数呢？因为最近公共祖先系列问题的解法都是把这个函数作为框架的。

2、秒杀五道题目

236. 二叉树的最近公共祖先

给你输入一棵不含重复值的二叉树，以及存在于树中的两个节点 p 和 q，请你计算 p 和 q 的最近公共祖先节点。

比如输入这样一棵二叉树：

如果 p 是节点 6，q 是节点 7，那么它俩的 LCA 就是节点 5：

当然，p 和 q 本身也可能是 LCA，比如这种情况 q 本身就是 LCA 节点：

两个节点的最近公共祖先其实就是这两个节点向根节点的「延长线」的交汇点，那么对于任意一个节点，它怎么才能知道自己是不是 p 和 q 的最近公共祖先？

如果一个节点能够在它的左右子树中分别找到 p 和 q，则该节点为 LCA 节点。

这就要用到之前实现的 find 函数了，只需在后序位置添加一个判断逻辑，即可改造成寻找最近公共祖先的解法代码：

【python】

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':return self.find(root, p.val, q.val)# 在二叉树中寻找 val1 和 val2 的最近公共祖先节点def find(self, root: 'TreeNode', val1: int, val2: int) -> 'TreeNode':if not root:return None# 前序位置if root.val == val1 or root.val == val2:# 如果遇到目标值，直接返回return rootleft = self.find(root.left, val1, val2)right = self.find(root.right, val1, val2)# 后序位置，已经知道左右子树是否存在目标值if left and right:# 当前节点是 LCA 节点return rootreturn left if left else right

在 find 函数的后序位置，如果发现 left 和 right 都非空，就说明当前节点是 LCA 节点，即解决了第一种情况：

在 find 函数的前序位置，如果找到一个值为 val1 或 val2 的节点则直接返回，恰好解决了第二种情况：

因为题目说了 p 和 q 一定存在于二叉树中（这点很重要），所以即便我们遇到 q 就直接返回，根本没遍历到 p，也依然可以断定 p 在 q 底下，q 就是 LCA 节点。

这样，标准的最近公共祖先问题就解决了，接下来看看这个题目有什么变体。

1676. 二叉树的最近公共祖先 IV

依然给你输入一棵不含重复值的二叉树，但这次不是给你输入 p 和 q 两个节点了，而是给你输入一个包含若干节点的列表 nodes（这些节点都存在于二叉树中），让你算这些节点的最近公共祖先。

函数签名如下：

def lowestCommonAncestor(root: TreeNode, nodes: List[TreeNode]) -> TreeNode:

比如还是这棵二叉树：

输入 nodes = [7,4,6]，那么函数应该返回节点 5。

看起来怪吓人的，实则解法逻辑是一样的，把刚才的代码逻辑稍加改造即可解决这道题：

【python】

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':# 将列表转化成哈希集合，便于判断元素是否存在values = set()for node in nodes:values.add(node.val)return self.find(root, values)def find(self, root: 'TreeNode', values: 'set') -> 'TreeNode':if not root:return None# 前序位置if root.val in values:return rootleft = self.find(root.left, values)right = self.find(root.right, values)# 后序位置，已经知道左右子树是否存在目标值if left and right:# 当前节点是 LCA 节点return rootreturn left if left else right

不过需要注意的是，这两道题的题目都明确告诉我们这些节点必定存在于二叉树中，如果没有这个前提条件，就需要修改代码了。

1644. 二叉树的最近公共祖先 II

给你输入一棵不含重复值的二叉树的，以及两个节点 p 和 q，如果 p 或 q 不存在于树中，则返回空指针，否则的话返回 p 和 q 的最近公共祖先节点。

在解决标准的最近公共祖先问题时，我们在 find 函数的前序位置有这样一段代码：

// 前序位置
if (root.val == val1 || root.val == val2) {// 如果遇到目标值，直接返回return root;
}

我也进行了解释，因为 p 和 q 都存在于树中，所以这段代码恰好可以解决最近公共祖先的第二种情况：

但对于这道题来说，p 和 q 不一定存在于树中，所以你不能遇到一个目标值就直接返回，而应该对二叉树进行完全搜索（遍历每一个节点），如果发现 p 或 q 不存在于树中，那么是不存在 LCA 的。

回想我在文章开头分析的几种 find 函数的写法，哪种写法能够对二叉树进行完全搜索来着？

这种：

def find(root: TreeNode, val: int) -> TreeNode:if not root:return None# 先去左右子树寻找left = find(root.left, val)right = find(root.right, val)# 后序位置，判断 root 是不是目标节点if root.val == val:return root# root 不是目标节点，再去看看哪边的子树找到了return left if left else right

那么解决这道题也是类似的，我们只需要把前序位置的判断逻辑放到后序位置即可：

【python】

class Solution:def __init__(self):# 用于记录 p 和 q 是否存在于二叉树中self.foundP = Falseself.foundQ = Falsedef lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:res = self.find(root, p.val, q.val)if not self.foundP or not self.foundQ:return None# p 和 q 都存在二叉树中，才有公共祖先return res# 在二叉树中寻找 val1 和 val2 的最近公共祖先节点def find(self, root, val1, val2):if not root:return Noneleft = self.find(root.left, val1, val2)right = self.find(root.right, val1, val2)# 后序位置，判断当前节点是不是 LCA 节点if left and right:return root# 后序位置，判断当前节点是不是目标值if root.val == val1 or root.val == val2:# 找到了，记录一下if root.val == val1:self.foundP = Trueif root.val == val2:self.foundQ = Truereturn rootreturn left if left else right

这样改造，对二叉树进行完全搜索，同时记录 p 和 q 是否同时存在树中，从而满足题目的要求。

接下来，我们再变一变，如果让你在二叉搜索树中寻找 p 和 q 的最近公共祖先，应该如何做呢？

235. 二叉搜索树的最近公共祖先

给你输入一棵不含重复值的二叉搜索树，以及存在于树中的两个节点 p 和 q，请你计算 p 和 q 的最近公共祖先节点。

把之前的解法代码复制过来肯定也可以解决这道题，但没有用到 BST「左小右大」的性质，显然效率不是最高的。

在标准的最近公共祖先问题中，我们要在后序位置通过左右子树的搜索结果来判断当前节点是不是 LCA：

对于 BST 来说，根本不需要老老实实去遍历子树，由于 BST 左小右大的性质，将当前节点的值与 val1 和 val2 作对比即可判断当前节点是不是 LCA：

假设 val1 < val2，那么 val1 <= root.val <= val2 则说明当前节点就是 LCA；若 root.val 比 val1 还小，则需要去值更大的右子树寻找 LCA；若 root.val 比 val2 还大，则需要去值更小的左子树寻找 LCA。

依据这个思路就可以写出解法代码：

【python】

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 保证 val1 较小，val2 较大val1 = min(p.val, q.val)val2 = max(p.val, q.val)return self.find(root, val1, val2)# 在 BST 中寻找 val1 和 val2 的最近公共祖先节点def find(self, root: 'TreeNode', val1: int, val2: int) -> 'TreeNode':if not root:return Noneif root.val > val2:# 当前节点太大，去左子树找return self.find(root.left, val1, val2)if root.val < val1:# 当前节点太小，去右子树找return self.find(root.right, val1, val2)# val1 <= root.val <= val2# 则当前节点就是最近公共祖先return root

1650. 二叉树的最近公共祖先 III

再看最后一道最近公共祖先的题目吧，力扣第 1650 题「二叉树的最近公共祖先 III」，这次输入的二叉树节点比较特殊，包含指向父节点的指针。题目会给你输入一棵存在于二叉树中的两个节点 p 和 q，请你返回它们的最近公共祖先。函数签名如下：

class Node:def __init__(self):self.val = Noneself.left = Noneself.right = Noneself.parent = None# 函数签名
def lowestCommonAncestor(p: Node, q: Node) -> Node:

由于节点中包含父节点的指针，所以二叉树的根节点就没必要输入了。

这道题其实不是公共祖先的问题，而是单链表相交的问题，你把 parent 指针想象成单链表的 next 指针，题目就变成了：

给你输入两个单链表的头结点 p 和 q，这两个单链表必然会相交，请你返回相交点。

 【python】

class Solution:def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':# 施展链表双指针技巧a, b = p, qwhile a != b:# a 走一步，如果走到根节点，转到 q 节点a = q if a is None else a.parent# b 走一步，如果走到根节点，转到 p 节点return a

3、总结

最近公共祖先问题，核心在于去理解p和q两个节点所处位置不同，引申出来的代码逻辑不同。

class Solution:def __init__(self):# 对于p,q 不确定有无得情况，需要额外加变量进行跟踪，并将find函数调整为后序遍历方式# 遇到p,q就更新这俩参数self.foundP = Falseself.foundQ = Falsedef lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':return self.find(root, p.val, q.val)# 在二叉树中寻找 val1 和 val2 的最近公共祖先节点def find(self, root: 'TreeNode', val1: int, val2: int) -> 'TreeNode':# 碰到叶子节点，返回None即可if not root:return None'''1、在前序位置遍历到目标值，不论是p还是q，直接返回该节点，其上层函数自有left或right做承接。2、即使给的不是val1和val2，而是一个list，依然只需判决该 root.val in list 即可返回root。3、若将此判决调到后序位置，则find方法会遍历所有节点，在不确定p,q是否存在的情况下用起来很方便。4、对于BST的最小公共祖先问题，只需明确p < q，root.val < p就去find右边，root.val > q就去find左边。'''if root.val == val1 or root.val == val2:# 如果遇到目标值，直接返回return root# find遍历便利的结果自然需要变量做承接，便于后续判决left = self.find(root.left, val1, val2)right = self.find(root.right, val1, val2)'''1、后续位置做left and right的判决，如果此节点left和right都存在，直接起一个截胡效果，不用继续向后遍历，直接确定该节点就是LCA并返回。2、即使给的不是val1和val2，而是一个list，即便某个节点的left and right各自只遍历到list中的一个值，放心地 return root, 因为自然会有上层函数通过这段代码进行“截胡”，依然能正确返回上层那个 left and right 都满足的节点。'''if left and right:# 当前节点是 LCA 节点return root'''1、当后序位置的 left and right判决迟迟未响应时，这行 return 代码做了最后的兜底。2、即使给的不是val1和val2，而是一个list，同理直接对该节点进行return，也是起一个兜底的效果。'''return left if left else right