Conditions for finding ca in bst:
9
/
5
/ \
3 8
3,8 ca is 5
5,3 ca is 9
static Node findDeepeastCommonAncestor(Node root, int d1, int d2){
if(root == null) return null;
if(!search(root, d1) || !search(root, d2)) return null;
if(d1 > d2)
{
int tmp = d1;
d1 = d2;
d2 = tmp;
}
return findDeepeastCommonAncestorUtil(root, d1, d2);
}
private static Node findDeepeastCommonAncestorUtil(Node root, int d1, int d2){
if(root == null) return null;
if(root.val > d1 && root.val < d2) return root;
if(root.val > d1 && root.val > d2)
{
if(root.left != null && root.left.val == d1) return root;
return findDeepeastCommonAncestorUtil(root.left, d1, d2);
}
if(root.val < d1 && root.val < d2)
{
if(root.right != null && root.right.val == d1) return root;
return findDeepeastCommonAncestorUtil(root.right, d1, d2);
}
return null;
}
private static boolean search(Node root, int data) {
if(root == null) return false;
if(root.val == data) return true;
if(root.val > data) return search(root.left, data);
return search(root.right, data);
}
No comments:
Post a Comment