private static int LCABTUtil(Node root, int n1, int n2)
{
//Base Condition
if(root == null) return 0;
int l = LCABTUtil(root.left, n1, n2);
int r = LCABTUtil(root.right, n1, n2);
// Node that has both n1 and n2 as descendants
if((l == 1 && r == 1))
{
System.out.println(root.data);
}
// If node to be a descendant of itself
else if((l == 1 || r == 1) && (root.data == n1 || root.data == n2))
{
System.out.println(root.data);
}
// Node that has one of descendant
else
{
if(l == 1 || r == 1)
{
return 1;
}
}
if(root.data == n1 || root.data == n2)
{
return 1;
}
return 0;
}
static void lcaBT(Node root, int n1, int n2)
{
LCABTUtil(root, n1, n2);
}
References:
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html
{
//Base Condition
if(root == null) return 0;
int l = LCABTUtil(root.left, n1, n2);
int r = LCABTUtil(root.right, n1, n2);
// Node that has both n1 and n2 as descendants
if((l == 1 && r == 1))
{
System.out.println(root.data);
}
// If node to be a descendant of itself
else if((l == 1 || r == 1) && (root.data == n1 || root.data == n2))
{
System.out.println(root.data);
}
// Node that has one of descendant
else
{
if(l == 1 || r == 1)
{
return 1;
}
}
if(root.data == n1 || root.data == n2)
{
return 1;
}
return 0;
}
static void lcaBT(Node root, int n1, int n2)
{
LCABTUtil(root, n1, n2);
}
References:
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html
No comments:
Post a Comment