bst_lowest_commona_ancestor
bst_lowest_commona_ancestor.go 源码
package main
//二叉搜索树的最近公共祖先
//递归
func bstLowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if p.Val < root.Val && q.Val < root.Val {
return bstLowestCommonAncestor(root.Left, p, q)
}
if p.Val > root.Val && q.Val > root.Val {
return bstLowestCommonAncestor(root.Right, p, q)
}
return root
}
//迭代
func bstLowestCommonAncestor2(root, p, q *TreeNode) *TreeNode {
for root != nil {
if p.Val < root.Val && q.Val < root.Val {
root = root.Left
} else if p.Val > root.Val && q.Val > root.Val {
root = root.Right
} else {
return root
}
}
return nil
}
你可能感兴趣的文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
8、 golang
-
9、 openharmony
-
10、 Vue中input框自动聚焦