Created
December 7, 2016 13:26
-
-
Save anhnguyen1618/cb76307a02683a4c2f79577e7bcf4c6f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
static Node lca(Node root,int v1,int v2) | |
{ | |
ArrayList<Node> list = new ArrayList<Node>(); | |
helper(root,v1,v2, list); | |
return list.get(list.size()-1); | |
} | |
static Node helper(Node node,int v1,int v2,ArrayList<Node> array){ | |
if(node.left == null && node.right == null){ | |
return null; | |
} | |
if(isParent(node,v1)&&isParent(node,v2) ){ | |
array.add(node); | |
} | |
if(node.left != null){ | |
helper(node.left,v1,v2, array); | |
} | |
if(node.right != null) { | |
helper(node.right,v1,v2, array); | |
} | |
return null; | |
} | |
static boolean isParent(Node node, int v1){ | |
if(node.left == null && node.right == null){ | |
return false; | |
} | |
if(node.data == v1){ | |
return true; | |
} | |
boolean hasLeft = false; | |
boolean hasRight = false; | |
if(node.left != null){ | |
hasLeft = isParent(node.left,v1); | |
} | |
if(node.right != null){ | |
hasRight = isParent(node.right,v1); | |
} | |
return hasLeft || hasRight; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment