题目
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
- 树中节点数目在范围 [2, 105] 内。
- -109 <= Node.val <= 109
- 所有 Node.val 互不相同 。
- p != q
- p 和 q 均存在于给定的二叉树中。
我的代码（Python）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or not p or not q:
return None
valSet = {p.val, q.val}
allRoute = []
routeCache = []
t = root
while t:
routeCache.append(t)
if t.val in valSet:
valSet.remove(t.val)
allRoute.append(routeCache[0:])
if not valSet:
break
if t.left:
t = t.left
elif t.right:
t = t.right
else:
t1 = routeCache.pop()
t = routeCache[-1]
while t.right == t1 or not t.right:
t1 = routeCache.pop()
t = routeCache[-1]
t = t.right
# print(f'allRoute[0]: {",".join([str(node.val) for node in allRoute[0]])}')
# print(f'allRoute[1]: {",".join([str(node.val) for node in allRoute[1]])}')
minLen = min(len(allRoute[0]), len(allRoute[1]))
for i in range(minLen):
if allRoute[0][i] != allRoute[1][i]:
return allRoute[0][i - 1]
return allRoute[0][minLen - 1]点评
深度优先搜索找到两条路径，然后比较路径上的最后一个相同结点。
和官方的第二种解法一致。这种解法的好处是，如果要找多个结点（不只两个），很容易扩展。
解法一的递归在这道题目里反而不太容易想到，解释也比较啰嗦，简单来说就是果一个结点的左右子树分别包含一个指定结点，这个结点就是要找的点。因为再往上一定是两个指定结点同在左或者右子树中，不会一边一个。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog