最低公共祖先 LCA

2.给定一棵二叉树和两个节点找出它们的最低公共祖先(LCA)。如果节点可能不存在于树中如何设计?1、背景介绍最近公共祖先Lowest Common Ancestor, LCA给定一棵根树和树上任意两个节点 u、v我们需要高效找到它们的最低公共祖先节点即在树中离根最远、深度最大且同时是 u 和 v 祖先的节点。2、LCA 典型应用场景文件系统路径管理查找两个文件 / 目录的最近公共父目录族谱分析确定两人最近的共同祖先网络路由优化计算树状网络中两个节点通信路径的汇聚点计算机图形学骨骼动画中查找两个骨骼的最近公共父骨骼在线查询系统树结构的区间查询、路径查询等高频 LCA 查询场景树结构问题解决树中节点间的路径查询、距离计算如结合DFS生物信息学基因树中分析物种进化关系。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(rootnull||proot||qroot){returnroot;}TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);if(left!nullright!null){returnroot;}return(left!null)?left:right;}publicstaticvoidmain(String[]args){// 构建测试树: [3,5,1,6,2,0,8,null,null,7,4]TreeNoderootnewTreeNode(3);root.leftnewTreeNode(5);root.rightnewTreeNode(1);root.left.leftnewTreeNode(6);root.left.rightnewTreeNode(2);root.right.leftnewTreeNode(0);root.right.rightnewTreeNode(8);root.left.right.leftnewTreeNode(7);root.left.right.rightnewTreeNode(4);SolutionsolutionnewSolution();// 测试用例1: p 5, q 1TreeNodeproot.left;// 节点5TreeNodeqroot.right;// 节点1TreeNoderesultsolution.lowestCommonAncestor(root,p,q);System.out.println(LCA of 5 and 1 is: result.val);// 输出: 3// 测试用例2: p 5, q 4TreeNodeq2root.left.right.right;// 节点4TreeNoderesult2solution.lowestCommonAncestor(root,p,q2);System.out.println(LCA of 5 and 4 is: result2.val);// 输出: 5// 测试用例3: 节点不存在的情况TreeNodenonExistentnewTreeNode(9);// 树中不存在的节点TreeNoderesult3solution.lowestCommonAncestor(root,p,nonExistent);System.out.println(LCA with non-existent node: (result3null?null:result3.val));// 输出: null}}解题思路递归方法从根节点开始递归地遍历左子树和右子树。如果当前节点是其中一个目标节点p或q则返回该节点如果在左子树和右子树中都找到了目标节点则当前节点就是LCA否则返回非null的子节点结果。关键点算法基于后序遍历左-右-根因为它需要先处理子树再处理根节点从而自底向上地确定LCA。边界条件如果树为空或目标节点不存在返回null如果目标节点是根节点则根节点就是LCA。算法流程基本检查若当前节点为 null返回 null若当前节点是 p 或 q返回当前节点命中目标递归遍历递归查找左子树获取结果递归查找右子树获取结果结果合并左、右结果均非空 → 当前节点是 LCA仅左结果非空 → 返回左子树结果仅右结果非空 → 返回右子树结果均为 null → 未找到目标节点返回 null总结本题核心解法是递归后序遍历逻辑简洁易实现适合二叉树 LCA 基础场景算法时间复杂度O(n)空间复杂度 O(h)递归栈海量查询场景可升级为倍增法大幅提升查询效率