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
}

你可能感兴趣的文章

combinations

generate_parentheses

invert_binary_tree