Derek
GO语言版本实现235
package main
import (
"fmt"
)
type TreeNode struct {
Left *TreeNode
Right *TreeNode
Val int
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// 说明找到了共同祖先
if root == nil || root == p || root == q {
return root
}
// 如果p和q都小于root,去左边找。如果p和q都大于root,去右边找。
if root.Val > max(p.Val, q.Val) {
return lowestCommonAncestor(root.Left, p, q)
} else if root.Val < min(p.Val, q.Val) {
return lowestCommonAncestor(root.Right, p, q)
} else {
return root
}
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func main() {
root := &TreeNode{
Val: 6,
Left: &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 0,
},
Right: &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 3,
},
Right: &TreeNode{
Val: 5,
},
},
},
Right: &TreeNode{
Val: 8,
Left: &TreeNode{
Val: 7,
},
Right: &TreeNode{
Val: 9,
},
},
}
fmt.Println(lowestCommonAncestor(root, root.Left, root.Right)) // 6
fmt.Println(lowestCommonAncestor(root, root.Left, root.Left.Right)) // 2
}