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
}

相关主题


返回:树算法 | 算法学习导航