最近公共祖先（LCA）
一句话说明
LCA 的本质是：谁第一次把
p和q从左右两边汇合起来，谁就是答案。
（附件 lca-path.svg 未随站点发布）
Go 代码：普通二叉树
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
}
if left != nil {
return left
}
return right
}Go 代码：BST 版本
func lowestCommonAncestorBST(root, p, q *TreeNode) *TreeNode {
for root != nil {
if p.Val < root.Val && q.Val < root.Val {
root = root.Left
continue
}
if p.Val > root.Val && q.Val > root.Val {
root = root.Right
continue
}
return root
}
return nil
}