第 71 题
二叉树结点含 LLINK、INFO、RLINK 三个域，ROOT、p、q 分别指向根和任意两个目标结点。编写 ANCESTOR(ROOT, p, q, r)，求 p 与 q 的最近公共祖先 r。
[tag_link]
参考答案
分别用 DFS 求根到 p、q 的路径；只有两条路径都存在时，扫描最后一个相同结点，它就是最近公共祖先。
伪代码
FindPath(T, target, path):
if T == null: return false
path.push(T)
if T == target: return true
if FindPath(T.left, target, path) or FindPath(T.right, target, path): return true
path.pop()
return false
Ancestor(root, p, q):
pathP = []; pathQ = []
foundP = FindPath(root, p, pathP)
foundQ = FindPath(root, q, pathQ)
if not foundP or not foundQ: return null
r = null
for i = 0 while i < min(length(pathP), length(pathQ)) and pathP[i] == pathQ[i]:
r = pathP[i]
return r
复杂度
两次 DFS 的时间 O(n)，两条路径和递归栈空间 O(h)。
边界条件
p 或 q 不在树中时返回 null；p=q 时返回该结点；其中一个目标是根时最近公共祖先为根；空树返回 null。
易错点
只根据值比较可能混淆重复值结点，本题参数是结点指针，应比较结点身份；还必须确认两个目标都存在。
评分要点
两次路径搜索；回溯时弹栈；校验 foundP/foundQ；取最长公共前缀末结点；覆盖根和缺失目标。