給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）?！?/p>

例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]

image.png

示例 1:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。
示例 2:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。

說明:

所有節(jié)點的值都是唯一的。
p、q 為不同節(jié)點且均存在于給定的二叉樹中。

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    if root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left == nil {
        return right
    }
    if right == nil {
        return left
    }
    if left != nil && right != nil {
        return root
    }
    return nil
}