在《剑指Offer》7.2 章中，面试案例：树中两个节点的最低公共祖先，记录了如下面试流程：
面试官：让我们做一个编程题目吧。输入树的两个节点，求他们的最低公共祖先。
面试者：这树是不是二叉树呢？
面试官：是又怎么样，不是又怎么样？
应聘者：如果是二叉树，并且是二叉搜索树，是可以找到公共节点的。
面试官：那假如就是二叉搜索树，你怎么查找呢？
二叉搜索树的查找:
func lowestCommonAncestor(root, p, q *structure.TreeNode) *structure.TreeNode {
if root == nil || p == nil || q == nil {
return nil
}
switch {
case q.Val < root.Val && p.Val < root.Val:
return lowestCommonAncestor(root.Left, p, q)
case q.Val > root.Val && p.Val > root.Val:
return lowestCommonAncestor(root.Right, p, q)
}
return root
}
面试官：看来你对这个题目很熟悉呢。
应聘者：这个碰巧。
面试官：那咱们稍微换一下，如果这棵树不是二叉搜索树，只是二叉树，又该怎么办？（此处我做了稍微的改动，原题为普通树）
二叉树：
func lowestCommonAncestor(root, p, q *structure.TreeNode) *structure.TreeNode {
if root == nil {
return nil
}
if root.Val == p.Val || root.Val == q.Val {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
switch {
case left == nil:
return right
case right == nil:
return left
}
return root
}
面试官：小伙汁，可以呀，那咱们在稍微改一下，如果这只是一颗普通的树呢？
应聘者：树的节点中有没有指向父节点的指针呢？
面试官：为什么需要指向父节点的指针？
应聘者：如果存在指向父节点的指针，这个问题可以转换成求两个链表的第一个公共节点。
……
链表
func getIntersectionNode(headA, headB *structure.ListNode) *structure.ListNode {
if headA == nil || headB == nil {
return nil
}
a, b := headA, headB
la, lb := 0, 0
for a != nil {
a = a.Next
la++
}
for b != nil {
b = b.Next
lb++
}
if la > lb {
abs := la - lb
for ; abs > 0; abs-- {
headA = headA.Next
}
} else {
abs := lb - la
for ; abs > 0; abs-- {
headB = headB.Next
}
}
for headA != nil && headB != nil {
if headA.Val == headB.Val {
return headA
}
headA = headA.Next
headB = headB.Next
}
return nil
}
面试官：那如果这就是颗普通的树，而且没有指向父节点的指针，你改如何处理？
应聘者：我们可以遍历整棵树，需找输入的两个节点p、q，将root节点到p、q的路径存储到两个链表，
这样就可以转换为上面的问题了，求两个链表的最近公共祖先。
……
参考资料