4.1 LCA I

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

Assumption: No parent pointer. Given two nodes are guaranteed to be in the tree.

Input: TreeNode root, one, and two

Output: TreeNode LCA

Solution:

1. Case 1: one and two are directly affiliated

Base case: if root == one || root == two, return root

Recursive rule: 1.1 If left && right return null, return null to current's parent

1.2 If either left/right return not null, return not null to current's parent

2. Case 2: one and two are not directly affiliated

Base case: if root == one || root == two, return root

if root == null, return root

Recursive rule:

2.1 If left && right return null, return null to current's parent

2.2 If either left/right return not null, return not null side to current's parent

2.3 If left && right return not null, return current

public TreeNode LCA(TreeNode root, TreeNode one, TreeNode two) {
  if (root == null || root == one || root == two) {
    return root;
  }
  TreeNode left = LCA(root.left, one, two);
  TreeNode right = LCA(root.right, one, two);
  if (left != null && right != null) {
    return root;
  }
  return left == null ? right : left;
}