Not a BST. Have to iterate through the whole tree.

  1. null, or p/q or not.
  2. Recursive results: left, right.

For left(or right), if left != null, 2 possibilities:

  1. p and q are both in left subtree, p or q is LCA;
  2. both in substree, a parent node of both is LCA;

No matter what it is, left is not null; same for right;

=>

  1. left, right are both not null: one in left subtree, one in right subtree. root is LCA;
  2. Both in left subtree: lowestCommonAncestor would recursively find the LCA in left subtree, then return;
  3. same as 2, in right subtree.
1
2
3
4
5
6
7
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}