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:

1. Same as in 4.1, if both return not null, current is the LCA.

2. 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;
}