企业官网建设流程全解析

wordpress 企业站模版,欧美网站设计特点,做软件与做网站建设有什么区别,深圳 网站开发公司【LeetCode 236】二叉树最近公共祖先#xff1a;我是如何用几行递归搞定这个面试高频题的#xff1f; 在二叉树的面试题中#xff0c;“最近公共祖先”#xff08;Lowest Common Ancestor#xff0c;简称 LCA#xff09;绝对是出现频率最高的题目之一。 初看题目#xf…【LeetCode 236】二叉树最近公共祖先我是如何用几行递归搞定这个面试高频题的在二叉树的面试题中“最近公共祖先”Lowest Common Ancestor简称 LCA绝对是出现频率最高的题目之一。初看题目可能觉得有点绕既要是祖先深度还要尽可能大。但其实只要我们转换一下视角用后序遍历自底向上的思维去理解这道题的代码逻辑简直优雅得让人惊叹。今天我就结合我写的这段 Java 代码带大家像剥洋葱一样拆解这道题的递归思路。1. 核心思维把“寻找”变成“汇报”解决这道题我的核心策略是**“自底向上汇报”**。你可以把每一个节点想象成一个部门经理。题目要求我们在整棵树里找p和q。作为根节点大老板我不知道p和q在哪但我可以派我的左右手左子树和右子树去搜。我对左孩子说“你去你的辖区找找有没有p或者q只要看到其中一个就赶紧告诉我。”我对右孩子说“你也去你的辖区找找同上。”等他们回来汇报结果后我再根据情况做判断。这就是后序遍历的精髓先搜左右最后再处理根节点的逻辑。2. 代码深度拆解让我们看着代码一行一行来翻译我的“内心戏”。classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(rootnull)returnroot;if(rootp||rootq)returnroot;TreeNodeleftTreelowestCommonAncestor(root.left,p,q);TreeNodeRightTreelowestCommonAncestor(root.right,p,q);if(leftTree!nullRightTree!null){returnroot;}elseif(leftTree!null){returnleftTree;}else{returnRightTree;}}}第一步终止条件遇到死胡同或找到目标if(rootnull)returnroot;// 或者 return nullif(rootp||rootq)returnroot;这是递归的**“触底反弹”**时刻。当我走到当前节点root时我有两个理由停止向下搜索到了空节点root null这里啥也没有死胡同返回null代码中写return root也是返回 null。找到了目标root p 或 root q这里有一个关键点如果我发现当前节点就是p或者q我不需要再往下找了。直接把我自己root返回上去。潜台词“报告长官我在这个位置发现了嫌疑人 P或者 Q”第二步下发任务递归搜索TreeNodeleftTreelowestCommonAncestor(root.left,p,q);TreeNodeRightTreelowestCommonAncestor(root.right,p,q);这两行代码就是“派人出去搜”。leftTree存的是左那边搜寻的结果。RightTree存的是右那边搜寻的结果。注意递归函数会一直钻到底直到触发第一步的终止条件才会带着结果一层层返回。第三步汇总决策我是不是祖先这是整段代码的灵魂也是很多人容易晕的地方。我现在拿到了左右手下的汇报结果leftTree和RightTree现在我要通过这三个if-else来判断情况情况 A左右都有发现 - 我就是 LCAif(leftTree!nullRightTree!null){returnroot;}如果leftTree不为空说明左边找到了一个而且RightTree也不为空说明右边也找到了一个。这意味着什么意味着p和q分别在我的左边和右边。既然一个在左一个在右那我不就是他们相遇的那个分岔路口吗所以我就是那个最近公共祖先直接返回我自己root。情况 B只有左边有发现 - 结果在左边elseif(leftTree!null){returnleftTree;}如果左边回报说“找到了”而右边回报说“全是 null”。说明p和q都在我的左子树里或者其中一个在左边另一个根本不在树里但题目保证一定在。既然都在左边那我这个“当前节点”就不是最近的祖先真正的结果是左手汇报上来的那个节点。于是我做个顺水人情把leftTree继续往上传递。情况 C只有右边有发现或都为 null - 结果在右边else{returnRightTree;}同理如果左边是空的那结果一定在右边。直接把RightTree返回上去。3. 一个特殊的疑问如果一个节点是另一个的祖先怎么办有同学可能会问“如果p是5q是1而结构是5 - ... - 1你的代码会先遇到5就直接返回了不会去搜下面的1吗”你是对的但这正是代码巧妙的地方回顾一下终止条件if(root p || root q) return root;如果我先遇到了p比如节点 5我直接返回5。我根本不会去遍历5的子树所以我也不会去刻意找q。但在这种情况下p本身就是p和q的最近公共祖先。所以直接返回p是完全正确的逻辑代码自动涵盖了“一个节点是另一个节点祖先”的特殊情况。4. 总结这段代码虽然短但逻辑非常严密遇到 null- 返回 null。遇到 p 或 q- 返回当前节点找到了。左搜右搜- 拿到左右结果。左有且右有- 当前节点就是答案LCA。一边有一边无- 答案在有结果的那一边。这就是利用二叉树后序遍历解决 LCA 问题的全部奥秘。与其死记硬背不如想象成一个“下属汇报、上级决策”的过程是不是瞬间清晰了很多希望这篇博客能帮你彻底拿下这道 LeetCode 高频题