最低公共祖先 LCA

2.给定一棵二叉树和两个节点，找出它们的最低公共祖先(LCA)。如果节点可能不存在于树中，如何设计?

1、背景介绍

最近公共祖先（Lowest Common Ancestor, LCA）：给定一棵根树和树上任意两个节点 u、v，我们需要高效找到它们的最低公共祖先节点：即在树中离根最远、深度最大，且同时是 u 和 v 祖先的节点。

2、LCA 典型应用场景

1. 文件系统路径管理：查找两个文件 / 目录的最近公共父目录；
2. 族谱分析：确定两人最近的共同祖先；
3. 网络路由优化：计算树状网络中两个节点通信路径的汇聚点；
4. 计算机图形学：骨骼动画中查找两个骨骼的最近公共父骨骼；
5. 在线查询系统：树结构的区间查询、路径查询等高频 LCA 查询场景；
6. 树结构问题：解决树中节点间的路径查询、距离计算（如结合DFS）；
7. 生物信息学：基因树中分析物种进化关系。

3、算法优化说明

• 暴力法：单次查询时间复杂度 O(h)（h 为树高），海量查询效率低
• 优化算法：倍增法、欧拉序 + RMQ、Tarjan 离线算法等
• 重点推荐：二进制倍增法，预处理复杂度 O(log⁡n)，单次查询复杂度O(log⁡n)，大数据场景性能优异

方法1: 暴力法(DFS回溯)

思路: 分别记录根节点到目标节点的路径，最后比较路径的交点。
时间复杂度:

• 预处理: 无
• 单次查询: O(n)

方法2: 倍增算法(高效查询)

思路: 预处理每个节点的2^k级祖先，通过二进制跳跃逼近LCA。
时间复杂度:

• 预处理: O(nlog n)
• 单次查询: O(log n)

方法3: Tarjan算法(离线查询)

思路: 基于并查集的DFS后序遍历，适合批量查询。
时间复杂度:

• 预处理与查询: O(n + qα(n)) (近似线性)

LeetCode 236. 二叉树的最近公共祖先

给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

最近公共祖先定义：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root==null||p==root||q==root){returnroot;}TreeNodeleft=lowestCommonAncestor(root.left,p,q);TreeNoderight=lowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null){returnroot;}return(left!=null)?left:right;}publicstaticvoidmain(String[]args){// 构建测试树: [3,5,1,6,2,0,8,null,null,7,4]TreeNoderoot=newTreeNode(3);root.left=newTreeNode(5);root.right=newTreeNode(1);root.left.left=newTreeNode(6);root.left.right=newTreeNode(2);root.right.left=newTreeNode(0);root.right.right=newTreeNode(8);root.left.right.left=newTreeNode(7);root.left.right.right=newTreeNode(4);Solutionsolution=newSolution();// 测试用例1: p = 5, q = 1TreeNodep=root.left;// 节点5TreeNodeq=root.right;// 节点1TreeNoderesult=solution.lowestCommonAncestor(root,p,q);System.out.println("LCA of 5 and 1 is: "+result.val);// 输出: 3// 测试用例2: p = 5, q = 4TreeNodeq2=root.left.right.right;// 节点4TreeNoderesult2=solution.lowestCommonAncestor(root,p,q2);System.out.println("LCA of 5 and 4 is: "+result2.val);// 输出: 5// 测试用例3: 节点不存在的情况TreeNodenonExistent=newTreeNode(9);// 树中不存在的节点TreeNoderesult3=solution.lowestCommonAncestor(root,p,nonExistent);System.out.println("LCA with non-existent node: "+(result3==null?"null":result3.val));// 输出: null}}

解题思路

• 递归方法：从根节点开始，递归地遍历左子树和右子树。
  如果当前节点是其中一个目标节点（p或q），则返回该节点；
  如果在左子树和右子树中都找到了目标节点，则当前节点就是LCA；
  否则，返回非null的子节点结果。
• 关键点：算法基于后序遍历（左-右-根），因为它需要先处理子树，再处理根节点，从而自底向上地确定LCA。
• 边界条件：如果树为空或目标节点不存在，返回null；如果目标节点是根节点，则根节点就是LCA。

算法流程

1. 基本检查
   1. 若当前节点为 null，返回 null
   2. 若当前节点是 p 或 q，返回当前节点（命中目标）
2. 递归遍历
   1. 递归查找左子树，获取结果
   2. 递归查找右子树，获取结果
3. 结果合并
   1. 左、右结果均非空 → 当前节点是 LCA
   2. 仅左结果非空 → 返回左子树结果
   3. 仅右结果非空 → 返回右子树结果
   4. 均为 null → 未找到目标节点，返回 null

总结

1. 本题核心解法是递归后序遍历，逻辑简洁易实现，适合二叉树 LCA 基础场景
2. 算法时间复杂度O(n)，空间复杂度 O(h)（递归栈）
3. 海量查询场景可升级为倍增法，大幅提升查询效率