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,因为不能够确定p,q是在左子树还是右子树上,所以要分别求出left和right,最后对left和right是否为null是否等于p,q判断来得出LCA。

但是BST本身,它的所有左儿子都<root<右儿子,所以能够根据三个点值的大小来确定LCA是在左子树还是在右子树上,优化了搜索。

  • 当root值大于p和q的值的时候,lca在root的左边
  • 当root值小于p和q的值的时候,lca在root的右边
  • 当root的值等于p或者q的时候,lca为root
  • 当root的值处于p和q中间的时候,lca为root
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);
}
//root等于p或q或者root的值在p和q中间.
return root;
}

none recursive的方法, 就直接一个while loop把上面的逻辑实现一下就可以了.不需要任何额外的stack或者queue.

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: