LeetCode 热题 HOT 100 （4）1

【LeetCode 热题HOT 100（4）1】主要涉及了几个算法问题，包括二叉树的最近公共祖先、除自身以外数组的乘积以及滑动窗口最大值。这些问题都是数据结构与算法领域常见的面试题目，下面将逐一详细解析。 **236. 二叉树的最近公共祖先** 这是关于二叉树的问题，目标是找到给定二叉树中两个指定节点的最近公共祖先。解决这个问题的关键在于递归。对于节点p和q，有以下三种情况： 1. p和q都在根节点的子树中，且分别位于左右两侧。 2. p是根节点，q在根的左或右子树中。 3. q是根节点，p在根的左或右子树中。 递归算法思路是：分别在左子树和右子树中寻找p和q，如果它们分别位于左右子树，那么最近公共祖先就是当前根节点；如果仅在左子树或右子树中找到一个，那么继续在未找到的子树中查找。C++代码实现中，函数`lowestCommonAncestor()`采用递归的方式，如果找到一个节点或到达空节点，都会返回相应的结果。 **238. 除自身以外数组的乘积** 这个问题要求计算数组中每个元素除去自身后的乘积。可以使用前缀积的概念来解决。首先创建一个前缀积数组p，p[i]表示数组nums[0]到nums[i-1]的乘积。然后从数组末尾开始，用变量s记录当前位置及之后的乘积，更新p数组。C++代码中，先初始化p数组，然后倒序遍历数组，依次更新p[i]并累积s。最终返回p数组。 **滑动窗口最大值** 给定数组nums和窗口大小k，我们需要找出所有滑动窗口中的最大值。朴素方法是每次移动窗口时遍历一次窗口，但效率较低。优化方案是使用双端队列（deque）来维护窗口内的元素。当新元素加入窗口时，将队列中的较小元素移除，同时保持队列始终存储窗口内的最大值。这样，每次队列头部的元素即为当前窗口的最大值。C++代码中，使用deque并维护其最大值状态，当窗口滑动时，快速更新最大值。 总结来说，这些LeetCode热题考察了二叉树的遍历、数组处理以及高效数据结构的应用。理解和掌握这些解题思路，对于提升编程能力、应对算法面试非常有帮助。