4.4 LCA IV

Given k nodes in a binary tree, find their lowest common ancestor.

Assumptions: k >= 2. No parent pointer. Given K nodes are guaranteed to be in the tree.

Input: TreeNode root, List<TreeNode> nodes

Output: TreeNode LCA of k nodes

Solution:

1. Use a set to store all nodes for efficient look up.

2. Same as 4.1. Base case: if root == null || set.contains(root), return root

public TreeNode LCA(TreeNode root, List<TreeNode> nodes) {
  Set<TreeNode> set = new HashSet<>(nodes);
  return helper(root, set);
}

private TreeNode helper(TreeNode root, Set<TreeNode> set) {
  if (root == null || set.contains(root)) { return root; }
  TreeNode left = helper(root.left, set);
  TreeNode right = helper(root.right, set);
  if (left != null && right != null) { return root; }
  return left == null ? right : left;
}