4.3 LCA III
Given two nodes in a binary tree, find their lowest common ancestor (the given two nodes are not guaranteed to be in the binary tree).
Assumptions: No parent pointer. Given two nodes are not guaranteed to be in the tree. Return null if any of the nodes is not in the tree.
Input: TreeNode root, one, two
Output: If exist in the same tree, return LCA, if not, return null
Solution:
Same as in 4.1, if both return not null, current is the LCA.
If it returns one or two, check if two or one is in its subtree by using a queue.
public TreeNode LCA(TreeNode root, TreeNode one, TreeNode two) {
Treenode res = helper(root, one, two);
if (res != one && res != two) { return res; }
boolean exist = false;
if (res == one) { exist = find (one, two); }
if (res == two) { exist = find (two, one}; }
return exist ? res : null; // if the other node is in its subtree, return itself
}
private TreeNode helper(TreeNode root, TreeNode one, TreeNode two) {
if (root == null || root == one || root == two) { return root; }
TreeNode left = helper(root.left, one, two);
TreNode right = helper(root.right, one, two);
if (left != null && right != null) { return root; }
return left == null ? right : left;
}
private boolean exist(TreeNode root, TreeNode node) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur == null) {
return true;
}
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
return false;
}
Last updated
Was this helpful?