Given a binary tree and two nodes p and q, find their lowest common ancestor (the deepest node that has both p and q as descendants, where a node can be a descendant of itself).
Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: 5 and 1 are direct children of 3, so 3 is their LCA.
The number of nodes is in the range [2, 10^5]p and q both exist in the tree and are distinctA recursive search naturally answers 'does this subtree contain p or q (or both)?' — build the LCA logic on top of that.
If a node's left subtree contains one target and its right subtree contains the other, that node itself IS the LCA — think about why.
If a subtree search returns one of the targets directly, that's also a valid signal to propagate upward — the found node could itself be an ancestor of the other target higher up.
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; // p and q found in DIFFERENT subtrees — root is the split point, hence the LCA
return left != null ? left : right; // both targets (or the only one found so far) are on one side — propagate that up
}Time: O(n) · Space: O(h)