Lowest Common Ancestor of a Binary Search Tree

Leave a comment

November 20, 2016 by oneOokay

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.


适用于所有binary tree的LCA方法这里。对于普通的binary tree,因为不能够确定pq是在左子树还是右子树上,所以得分别求出left和right,最后对left和right进行判断来得出LCA。

但是BST本身,它的所有左儿子都<root<右儿子,所以能够根据值的大小来确定LCA是在左子树还是在右子树上,优化了搜索。所以不需要分左右,直接能够知道是应该往左还是往右搜寻。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left, p, q);
}
if (root.val < p.val && root.val < q.val){
return lowestCommonAncestor(root.right, p, q);
}
return root;
}

none recursive的方法

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 while (true){
 if (root.val > p.val && root.val > q.val){
 root = root.left;
 } else if (root.val < p.val && root.val < q.val){
 root = root.right;
 } else {
 return root;
 }
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: