BST的最近公共祖先
一句话说明
BST 的 LCA 只看大小关系:两边都小就往左,两边都大就往右,否则当前节点就是答案。
Go 代码
func lowestCommonAncestor(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
}