企业官网建设流程全解析

如何进行电子商务网站建设规划,国家林业工程建设协会网站,php网站登录系统怎么做,宁夏网站建设报价【LeetCode热题100】Java详解#xff1a;二叉树的最近公共祖先#xff08;含递归/父指针双解法与工程实践#xff09; 面向人群 正在准备技术面试#xff08;尤其是大厂后端、算法岗#xff09;的开发者已掌握二叉树基本遍历#xff0c;希望深入理解LCA#xff08;最近…【LeetCode热题100】Java详解二叉树的最近公共祖先含递归/父指针双解法与工程实践面向人群正在准备技术面试尤其是大厂后端、算法岗的开发者已掌握二叉树基本遍历希望深入理解LCA最近公共祖先算法的学习者刷 LeetCode「热题100」或「二叉树专题」的中级程序员对递归思想、树形DP感兴趣的工程人员 本文适合已能手写二叉树DFS遍历的读者。若对递归、哈希表不熟悉建议先完成 LeetCode 第235题二叉搜索树的最近公共祖先和第104题二叉树的最大深度。关键词LeetCode 236、二叉树的最近公共祖先、LCA、递归、父指针、深度优先搜索、树形DP、面试高频题、时间复杂度分析阅读前必须掌握的基础在深入阅读本文前请确保你已熟练掌握以下知识点二叉树的基本操作DFS遍历前序、中序、后序递归实现树遍历树节点的定义和基本操作递归思想递归终止条件递归返回值的含义自底向上的递归处理Java 基础数据结构HashMap的基本操作put,getHashSet的基本操作add,contains递归栈的工作原理复杂度分析能分析 O(n) 时间复杂度理解递归栈空间复杂度✅ 推荐前置练习LeetCode 235二叉搜索树的最近公共祖先LeetCode 104二叉树的最大深度LeetCode 112路径总和一、原题回顾题目链接236. 二叉树的最近公共祖先题目描述给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科定义“对于有根树 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 。可视化树结构3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4示例 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提示树中节点数目在范围[2, 10⁵]内-10⁹ Node.val 10⁹所有Node.val互不相同p ! qp和q均存在于给定的二叉树中二、原题分析2.1 核心概念理解最近公共祖先LCA的关键特性祖先关系LCA必须是p和q的共同祖先深度最大在所有公共祖先中LCA的深度最大离叶子最近自包含性如果p是q的祖先那么p就是LCA2.2 问题的难点普通二叉树没有BST那样的有序性质无法通过值的大小判断方向任意位置p和q可以在树的任意位置包括同一子树或不同子树自包含情况需要正确处理一个节点是另一个节点祖先的情况2.3 解题思路的核心洞察对于任意节点x要成为p和q的LCA必须满足以下两种情况之一情况1p和q分别在x的左右子树中左子树包含p右子树包含q或反之此时x就是LCA情况2x本身就是p或q且另一个节点在其子树中x p且q在x的子树中x q且p在x的子树中此时x就是LCA✅ 这个洞察是递归解法的基础三、答案构思两种主流解法本题有两种经典解法体现了递归思维 vs 数据结构思维的不同角度方法核心思想时间复杂度空间复杂度实现难度方法一递归推荐自底向上后序遍历树形DP思想O(N)O(N)中等方法二父指针 哈希表存储父节点信息模拟向上查找O(N)O(N)简单 两种方法时间复杂度相同但递归法更优雅父指针法更直观。四、完整答案与代码实现Java方法一递归后序遍历 树形DP思路详解这是最经典的解法采用后序遍历的思想递归函数定义dfs(root, p, q)返回布尔值表示以root为根的子树是否包含p或q递归过程先递归处理左子树得到lson再递归处理右子树得到rson检查当前节点是否满足LCA条件LCA判断条件(lson rson)p和q分别在左右子树((root p || root q) (lson || rson))当前节点是p或q且另一个在子树中关键技巧使用全局变量ans记录找到的LCA一旦找到就不再更新因为后序遍历保证第一次找到的就是深度最大的Java 代码标准版classSolution{privateTreeNodeans;publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){dfs(root,p,q);returnans;}/** * DFS遍历返回以root为根的子树是否包含p或q */privatebooleandfs(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull){returnfalse;}// 递归处理左右子树booleanlsondfs(root.left,p,q);booleanrsondfs(root.right,p,q);// 检查当前节点是否为LCAif((lsonrson)||((rootp||rootq)(lson||rson))){ansroot;}// 返回当前子树是否包含p或qreturnlson||rson||(rootp||rootq);}}Java 代码优化版 - 直接返回LCA有些面试官可能不喜欢使用全局变量我们可以直接让递归函数返回LCAclassSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){// 终止条件if(rootnull||rootp||rootq){returnroot;}// 递归处理左右子树TreeNodeleftlowestCommonAncestor(root.left,p,q);TreeNoderightlowestCommonAncestor(root.right,p,q);// 情况1p和q分别在左右子树if(left!nullright!null){returnroot;}// 情况2p和q在同一子树返回非空的那个returnleft!null?left:right;}}✅优化版的优势无需全局变量更符合函数式编程思想代码更简洁逻辑更清晰同样保证O(N)时间复杂度执行过程图解示例1以p5, q1为例后序遍历顺序6→7→4→2→5→0→8→1→3 访问6: 不是5或1返回false 访问7: 不是5或1返回false 访问4: 不是5或1返回false 访问2: 左false, 右false, 自己不是5/1 → 返回false 访问5: 自己是5 → 返回true (此时lsonfalse, rsonfalse) 访问0: 不是5或1返回false 访问8: 不是5或1返回false 访问1: 自己是1 → 返回true 访问3: lsontrue(来自5), rsontrue(来自1) → 满足lsonrson → ans3方法二父指针 哈希表思路详解这个方法更直观模拟了从下往上找的过程预处理遍历整棵树用哈希表记录每个节点的父节点标记路径从p开始沿着父指针向上标记所有访问过的节点查找交点从q开始沿着父指针向上第一个被标记的节点就是LCA为什么这样工作从p到根的路径和从q到根的路径它们的第一个交点就是LCA这类似于链表相交问题的解法Java 代码classSolution{// 存储每个节点的父节点privateMapTreeNode,TreeNodeparentMapnewHashMap();// 存储从p到根路径上访问过的节点privateSetTreeNodevisitednewHashSet();publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){// 构建父节点映射buildParentMap(root);// 从p向上遍历标记所有祖先TreeNodecurrentp;while(current!null){visited.add(current);currentparentMap.get(current);}// 从q向上遍历找到第一个已访问的节点currentq;while(current!null){if(visited.contains(current)){returncurrent;}currentparentMap.get(current);}returnnull;// 理论上不会执行到这里}/** * DFS遍历构建父节点映射 */privatevoidbuildParentMap(TreeNodenode){if(nodenull){return;}if(node.left!null){parentMap.put(node.left,node);buildParentMap(node.left);}if(node.right!null){parentMap.put(node.right,node);buildParentMap(node.right);}}}执行过程图解示例2以p5, q4为例构建父节点映射 5.parent 3 6.parent 5, 2.parent 5 7.parent 2, 4.parent 2 1.parent 3 0.parent 1, 8.parent 1 从p5向上标记 visited {5, 3} 从q4向上查找 4 → 2 → 55在visited中→ 返回5五、代码分析与对比维度递归法父指针法时间复杂度O(N)O(N)空间复杂度O(N)O(N)代码简洁性⭐⭐⭐⭐⭐⭐⭐实现难度中等简单函数调用开销有递归栈无内存使用仅递归栈哈希表递归栈面试推荐度首选备选方案面试策略优先实现递归法展示算法思维如果面试官要求不用递归再提供父指针法重点解释递归法中的LCA判断条件六、时间复杂度与空间复杂度深度分析时间复杂度O(N)递归法每个节点被访问一次每次访问的操作是O(1)总计O(N)父指针法构建父节点映射O(N)从p向上遍历O(h)h为树高从q向上遍历O(h)总计O(N)空间复杂度O(N)递归法递归栈深度O(h)最坏O(N)链状树全局变量O(1)总计O(N)父指针法父节点哈希表O(N)visited集合O(h)递归栈构建父映射O(h)总计O(N)实际性能差异递归法常数因子更小实际运行更快父指针法在极端情况下超深树可能栈溢出风险更低七、常见问题解答FAQQ1为什么递归法使用后序遍历而不是前序遍历A因为我们需要先知道左右子树的信息才能判断当前节点是否为LCA。后序遍历左→右→根保证了在处理根节点时左右子树的信息已经计算完成。Q2递归法中的全局变量ans会不会被多次赋值A理论上会但实际上只有一次有效赋值。因为后序遍历是从底向上的第一个满足条件的节点就是深度最大的LCA。即使后续更高层的节点也满足条件但由于题目保证p和q都存在所以不会出现多个有效的LCA。Q3如果树中有重复值怎么办A题目保证所有Node.val互不相同所以不用担心。但在实际工程中我们应该比较节点引用而不是节点值.val这在我们的代码中已经正确处理了。Q4能否用BFS替代DFSA可以但实现更复杂。BFS无法自然地进行自底向上的处理需要额外的数据结构来存储层次信息。Q5父指针法的空间复杂度真的是O(N)吗A是的。虽然visited集合最多只存储O(h)个元素但parentMap需要存储N-1个父节点映射所以总体空间复杂度是O(N)。八、优化思路总结8.1 代码优化避免全局变量使用直接返回LCA的递归版本早期终止在找到LCA后可以考虑提前终止但实现复杂收益不大类型安全始终比较节点引用而非节点值8.2 性能优化迭代替代递归对于超深树可以用显式栈避免栈溢出内存优化父指针法中visited可以用位图优化但节点值范围太大不实用8.3 健壮性优化输入验证检查p和q是否真的存在于树中题目已保证异常处理处理空树、空节点等边界情况九、数据结构与算法基础知识点回顾9.1 树的遍历方式对比遍历方式访问顺序适用场景前序遍历根→左→右复制树、序列化后序遍历左→右→根删除树、计算子树信息中序遍历左→根→右BST排序输出✅ LCA问题天然适合后序遍历因为需要子树信息来决定根节点的行为。9.2 树形动态规划Tree DPLCA的递归解法实际上是树形DP的一个简单例子状态定义f(root) 以root为根的子树是否包含p或q状态转移f(root) f(left) || f(right) || (root p || root q)答案提取在状态转移过程中根据特定条件提取最终答案9.3 路径相交问题父指针法将LCA问题转化为两条路径的相交问题路径1p → root路径2q → root求两条路径的第一个交点这与LeetCode 160相交链表的思想完全一致。十、面试官提问环节模拟Q你的递归解法中为什么不需要检查p和q是否存在于树中A题目明确说明p和q均存在于给定的二叉树中所以我们不需要做额外的存在性检查。但在实际工程中这是一个重要的边界条件应该添加相应的验证逻辑。Q如果要求找到k个节点的LCA你的解法还能工作吗A递归法可以扩展。对于k个节点我们需要统计当前子树中包含了多少个目标节点。当某个节点的子树恰好包含所有k个节点且它的子节点都不满足这个条件时该节点就是LCA。Q能否将空间复杂度优化到O(1)A在一般二叉树中很难做到O(1)空间复杂度。但如果树节点包含父指针那么父指针法的空间复杂度可以降到O(h)只需要visited集合。不过题目给出的TreeNode定义没有父指针。Q你的优化版递归代码中为什么if (root null || root p || root q)可以直接返回rootA这是一个巧妙的剪枝如果root为null说明没找到目标节点如果root等于p或q说明找到了目标节点直接返回这样可以避免不必要的递归并且正确处理了一个节点是另一个节点祖先的情况十一、实际开发中的应用场景11.1 文件系统路径解析在目录树中找到两个文件的最近公共目录实现commonPrefix功能用于相对路径计算版本控制系统中的分支合并点查找11.2 DOM树操作在HTML DOM树中找到两个元素的最近公共祖先实现事件委托时确定事件处理的最佳位置CSS选择器引擎中的祖先匹配11.3 组织架构管理在公司组织架构树中找到两个员工的最近共同上级权限系统中的角色继承关系分析审批流程中的共同审批人确定11.4 编译器AST抽象语法树在AST中找到两个表达式的最近公共作用域变量作用域分析和符号表管理代码优化中的公共子表达式识别11.5 网络路由协议在网络拓扑树中找到两个节点的最优汇聚点多播路由中的汇聚路由器选择CDN节点选择中的最优边缘节点确定十二、相关题目推荐题号题目关联点235二叉搜索树的最近公共祖先BST特殊性质1650二叉树的最近公共祖先 III节点包含父指针1676二叉树的最近公共祖先 IV多个节点的LCA1644二叉树的最近公共祖先 IIp或q可能不存在236本题普通二叉树LCA 学习路径建议235 → 236 → 1650 → 1676十三、总结与延伸13.1 核心思想提炼递归思维自底向上后序遍历利用子树信息决策分类讨论LCA的两种情况必须都考虑到树形DP将复杂问题分解为子问题的典型应用路径相交将树问题转化为路径问题的巧妙转换13.2 延伸思考动态LCA支持在线插入/删除节点的LCA查询批量LCA预处理后支持O(1)查询任意两点LCATarjan算法、倍增算法带权LCA路径上有权重求最小权重的公共祖先分布式LCA在分布式系统中处理超大树的LCA查询13.3 面试答题建议展示完整的思考过程确认理解“LCA是指深度最大的公共祖先一个节点可以是自己的祖先对吗”分析性质解释LCA的两种情况画图说明提出方案先说递归思路强调后序遍历的必要性代码实现写出清晰的递归代码解释关键条件优化讨论提到父指针法作为备选方案复杂度分析准确分析时间和空间复杂度边界处理讨论特殊情况的处理LCA问题是树形数据结构的经典代表它不仅考察了对树遍历的理解更体现了分治思想和递归思维的精髓。掌握LCA的解法就掌握了处理树形结构中关系查询问题的核心能力