給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先硫惕。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p叁巨、q财岔，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p龟虎、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）璃谨。”
例如，給定如下二叉樹: 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
}
