二叉树的最近公共祖先（LCA）问题

题目描述
给定一个二叉树和两个节点p、q，要求找到它们的最近公共祖先（Lowest Common Ancestor，LCA）。最近公共祖先定义为同时是p和q祖先的节点中，深度最大的那个节点（一个节点可以是自己的祖先）。

解题思路

1. 递归后序遍历：从根节点开始递归遍历二叉树，在左右子树中查找p和q。
   • 若当前节点为p或q，则返回当前节点。
   • 若左右子树均找到目标节点（即左右返回值均非空），则当前节点为LCA。
   • 若仅一侧子树找到目标节点，则返回该侧结果。
2. 时间复杂度：O(N)，每个节点最多被访问一次。
3. 空间复杂度：O(H)，递归栈深度为树高H（最坏情况为O(N)）。

详细步骤

1. 终止条件：

   • 当前节点为空时返回null。
   • 当前节点为p或q时返回当前节点（说明找到目标）。

2. 递归左右子树：

   • 左子树递归查找p和q，得到结果left。
   • 右子树递归查找p和q，得到结果right。

3. 判断LCA：

   • 若left和right均非空：说明p和q分别位于当前节点两侧，当前节点为LCA。
   • 若left非空而right为空：说明p和q均在左子树，返回left。
   • 若right非空而left为空：说明p和q均在右子树，返回right。

示例
二叉树：[3,5,1,6,2,0,8,null,null,7,4]，p=5，q=1。

• 从根节点3开始：左子树返回5（找到p），右子树返回1（找到q），左右均非空，因此3是LCA。

代码实现（Java）

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; // 当前为LCA
    return left != null ? left : right; // 返回非空结果
}

关键点

• 利用后序遍历的“回溯”特性，自底向上传递目标节点信息。
• 若p是q的祖先，则递归时会先遇到p并直接返回，最终p作为结果传递到根节点。