0236.二叉树的最近公共祖先
难度：🟡 中等
标签：树、深度优先搜索、二叉树
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先（LCA）。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
解题思路
核心思想
本题的核心思想是利用 递归 和 深度优先搜索（DFS），通过后序遍历的方式从下至上地传递信息。对于任意一个节点 root，我们可以判断 p 和 q 在其子树中的分布情况：
如果
p和q分别位于root的左右子树中，那么root就是它们的最近公共祖先。如果
p和q都位于root的左子树中，那么问题就转化为在左子树中寻找它们的最近公共祖先。如果
p和q都位于root的右子树中，问题同理。如果
root本身就是p或q，那么它也可能是最近公共祖先。
思路选择
递归法 是解决此问题最优雅、最简洁的思路。我们可以定义一个递归函数，其功能是：如果在以 root 为根的树中能找到 p 或 q，就返回找到的那个节点；如果都能找到，就返回它们的LCA；如果都找不到，就返回 null。
关键步骤
递归终止条件 (Base Case)： a. 如果当前
root为null，说明在这条路径上没找到任何节点，返回null。 b. 如果当前root恰好等于p或q，那么root就是一个潜在的LCA，直接返回root。递归分解： a. 向左子树递归，
leftLowest = lowestCommonAncestor(root.left, p, q)。 b. 向右子树递归，rightLowest = lowestCommonAncestor(root.right, p, q)。结果合并：根据左右子树的返回结果进行判断： a. 如果
leftLowest和rightLowest都非空，说明p和q分别位于root的左右两侧，因此root就是LCA，返回root。 b. 如果leftLowest为空，rightLowest非空，说明p和q都在右子树，LCA也必然在右子树，返回rightLowest。 c. 如果rightLowest为空，leftLowest非空，说明p和q都在左子树，LCA也必然在左子树，返回leftLowest。 d. 如果两者都为空，说明p和q都不在此子树中，返回null。
代码实现
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
// Base Case 1: 树为空，或找到p或q
if (root === null || root === p || root === q) {
return root;
}
// 在左、右子树中递归寻找
let leftLowest = lowestCommonAncestor(root.left, p, q);
let rightLowest = lowestCommonAncestor(root.right, p, q);
// 如果p和q分别在左右子树，则root是LCA
if (leftLowest && rightLowest) {
return root;
}
// 如果p和q都在其中一个子树，则LCA在该子树中，返回那个非空的结果
// 如果p和q都不在root的子树中，leftLowest和rightLowest都将是null，最终返回null
return leftLowest || rightLowest;
};
复杂度分析
时间复杂度：O(n) 其中 n 是树的节点总数。该算法对树进行一次完整的后序遍历，每个节点仅访问一次。
空间复杂度：O(h) 其中 h 是树的高度。空间复杂度主要由递归调用栈的深度决定。在最坏情况下（树退化为一条链），递归深度为 n，空间复杂度为 O(n)；在最好的情况下（一个完全平衡的树），递归深度为 log(n)，空间复杂度为 O(log n)。
相关题目
0235.二叉搜索树的最近公共祖先 (利用BST特性可进行优化)
1644.二叉树的最近公共祖先 II (p, q 可能不存在于树中)
总结
本题是二叉树递归思想的集大成者。通过后序遍历的“自底向上”特性，递归函数能够巧妙地将子问题的解（在子树中是否找到了 p 或 q）传递给父节点，父节点再根据这些信息做出判断。这种“分解问题、解决子问题、合并解”的模式是递归算法的精髓。