本题采用后序遍历深度优先搜索分治算法又称“自底向上状态回溯法”解决二叉树中两个指定节点的最近公共祖先查找问题。其核心本质是将全局祖先交集判定拆解为左右子树包含属性的自底向上归纳利用递归返回值的非空状态进行路径交汇点锁定。当前提供的源码实现了在时间复杂度 O(n) 和额外空间复杂度 O(h)其中 h 为树的高度条件下的全局最优解搜索最终走向是精准定位并回传 p 和 q 的最近公共祖先节点指针。一、 问题本质与数据模型对于给定的二叉树以及两个明确存在的独立节点 p 和 q最近公共祖先LCA的求解面临拓扑交汇的物理约束自包含与排他属性若当前节点就是 p 或 q则它自身就是一个潜在的祖先节点其下方的子树无需进一步向下展开搜索。因为如果另一个目标节点存在于其子树中则当前节点自身即为最近公共祖先若不存在当前节点也是向上传递的唯一目标信号。路径交汇特征如果一个节点的左子树包含了 p或 q且右子树包含了 q或 p那么由于树结构单向分叉的物理特性该节点必然是 p 和 q 路径分离的分水岭即最近公共祖先。为了高效识别交汇点算法引入了“后序状态回溯模型”。自顶向下寻找目标节点一旦触底或命中目标则立即自底向上汇报状态。通过区分返回值是否为空null在父节点处进行逻辑判定破除了盲目全树搜索的低效困局。二、 算法演进对比在寻找二叉树最近公共祖先的场景中后序状态回溯法在时空资源的控制及逻辑完备性上表现优异解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷父节点指针路径求交法O(n)O(n)利用哈希表或遍历记录所有节点的父指针将问题转化为两个单链表求相交节点需要显式记录全树的父节点物理映射增加了额外的内存空间开销后序状态回溯法当前解法O(n)O(h)自底向上回溯通过左右子树返回值的非空状态判断目标节点的空间分布强依赖系统递归栈当树高度退化为单链表时栈深将达到 O(n)前序路径记录比对法O(n)O(h)深度优先搜索分别找出根节点到 p 和 q 的两条完整几何路径再对比找出最后一个公共节点需要在内存中完整维护两条路径数组回溯与数据同步的逻辑较为繁琐三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于后序回溯的分支拦截与归纳组合其内部决策分支证明如下1. 目标命中与基准退出分支if (root null || root p || root q)执行直接返回 root。物理意义当触及空边界或者当前节点正好就是目标节点 p 或 q 时无需继续向下探测。直接将当前节点指针向上层调用栈返回作为“在此路径上发现了目标信号”的物理证明。2. 左右子树独立探测TreeNode left lowestCommonAncestor(root.left, p, q);执行以并行分治的方式分别获取左子树和右子树中关于 p 和 q 的搜寻状态。数学证明后序遍历保证了子树的状态先于当前根节点被计算完毕。left和right的返回值不仅代表是否找到目标还代表了在子树中已经确定的局部 LCA 结果。3. 双侧交汇判定分支if (left ! null right ! null)执行直接返回 root。数学证明若left和right均不为空证明目标节点 p 和 q 分别位于当前 root 节点的左右两侧子树中。由于树结构的唯一父级导向性当前 root 节点就是它们在拓扑上首次相遇的交汇点因此当前 root 节点就是全局最近公共祖先立即向上传递。4. 单侧信号向上传递return (left ! null) ? left : right;执行若双侧未同时命中则返回那个非空的指针若均为空则返回 null。数学证明如果有一侧为空说明那一侧子树中完全不包含 p 或 q 的任何痕迹。那么如果另一侧非空非空侧返回的指针可能是 p、q 本身也可能是那一侧子树内部已经找出的 LCA就是当前层级所能获得的唯一有效信号必须继续向上传递以供更高级别的父节点进行双侧交汇判定。四、 算法执行状态机步进示例以输入二叉树root [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]寻找目标p 5,q 4为例LCA 预期为 5状态机的演进过程如下表所示步骤当前访问节点值触发的子操作 / 状态判定返回给上层的值空间调用栈物理状态说明初始3调用左子树 5进入挂起状态等待中栈深: [3]15触发命中条件root p不再向下探测直接返回自身节点 5栈深: [3, 5] - 弹出 523左子树返回了节点 5接着调用右子树 1进入挂起状态等待中栈深: [3]31递归左子树 0 和右子树 8均返回 null (触底及未命中)null栈深: [3, 1] - 弹出 143左子树返回 5右子树返回 null触发单侧信号传递节点 5栈深: [3] - 弹出 3流程结束五、 源码实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 基准收敛条件若当前节点为空或者命中了目标节点 p 或 q则直接返回当前节点 if (root null || root p || root q) { return root; } // 分治递归自顶向下推进获取左子树的最近公共祖先搜寻状态 TreeNode left lowestCommonAncestor(root.left, p, q); // 分治递归自顶向下推进获取右子树的最近公共祖先搜寻状态 TreeNode right lowestCommonAncestor(root.right, p, q); // 状态判定若左右子树的返回信号均不为空证明 p 和 q 分布在当前节点两侧当前节点即为交汇点 if (left ! null right ! null) { return root; } // 信号传递若未形成双侧交汇则将非空一侧的有效信号或 null向回溯层父节点呈递 return (left ! null) ? left : right; } }六、 复杂度分析1. 时间复杂度O(n)分析在最坏情况下如目标节点位于叶子节点或树完全有效合法时深度优先搜索算法会完整遍历二叉树中的所有节点。每个节点被访问的次数固定为常数次且在每个节点内执行的指针判空、逻辑对等比对以及三目运算符操作均为常数阶时间 O(1)。若二叉树共包含 n 个节点总操作步数与 n 呈严格的线性正比关系。结论时间复杂度定性为 O(n)实现了对未知拓扑树结构检索的最优线性收敛。2. 空间复杂度O(h)分析算法在堆内存中未申请任何额外的线性数据结构空间。其空间的动态开销完全取决于系统因递归调用而开辟的函数栈深度。递归栈的最大并行深度严格等价于二叉树的物理高度 h。在最坏情况下二叉树高度严重倾斜退化为单链表拓扑树高 h 等于 n在理想平衡状态下树高 h 被控制在对数阶层级。结论空间复杂度表示为 O(h)内存空间的动态波峰完全受限于输入树的拓扑高度特征。