网站内容与功能模块设计,工作站做网站,实体店线上线下运营模式,怎么做服装网站最近在刷leetcode hot100,在写二叉树中最大路径和的时候,看到了一个佬对递归的理解,深受启发,感觉自己对于递归的题又行了!!!
这里给大家分享一下(建立大家先去尝试一下这道题再来看
124. 二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每…最近在刷leetcode hot100,在写二叉树中最大路径和的时候,看到了一个佬对递归的理解,深受启发,感觉自己对于递归的题又行了!!!
这里给大家分享一下(建立大家先去尝试一下这道题再来看
124. 二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 返回其 最大路径和 。 示例 1
输入root [1,2,3]
输出6
解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6
示例 2
输入root [-10,9,20,null,null,15,7]
输出42
解释最优路径是 15 - 20 - 7 路径和为 15 20 7 42提示
树中节点数目范围是 [1, 3 * 104]-1000 Node.val 1000
ps:这道题感觉达不到困难的级别
但佬的解题思路就是清晰,让人豁然开朗,顿悟的不仅是这道题,而是递归 这道题说难也不难但说容易也真不是那么容易能想到的写得比较多但都是心得耐心看完就更上一层楼了。 首先就是递归的方式很多人都对递归一头雾水一看就会一写就废。不用担心这是正常现象。 下面我们详细解释一下这道题顺便疏通一下递归的基本思路。 我们不要先去考虑整个递归的代码怎么去写而是要明确一个递归的主体就是这个递归的主体要怎么构造然后再去想边界条件返回值等等。 1、那么首先我们可以假设走到了某个节点现在要面临的问题是路径的最大值问题显然对于这种问题每遍历到一个节点我们都要求出包含该节点在内的此时的最大路径并且在之后的遍历中更新这个最大值。对于该节点来说它的最大路径currpath就等于左右子树的最大路径加上本身的值也就是currpath leftrightnode,val但是有一个前提我们要求的是最大路径所以若是left或者right小于等于0了那么我们就没有必要把这些值加上了因为加上一个负数会使得最大路径变小。这里的最大路径中的最其实就是一个限定条件也就是我们常说的贪心算法只取最大最好其余的直接丢弃。 2、好了1中的主体我们已经明确了但是还存在一个问题那就是left和right具体应该怎么求也就是left和right的递归形式。显然我们要把node.left和node.right再次传输到递归函数中重复上述的操作。但如果到达了叶子节点是不是需要往上一层返回了呢那么返回值又是多少呢 我们要明确left和right的基本含义它们表示的是最大贡献那么一个节点的最大贡献就等于node.valmax(left,right)这个节点本身选上然后从它的左右子树中选择最大的那个加上。 对于叶子节点也是这样但是叶子节点的左右子树都为空所以加上0哎注意看此时是不是边界条件也出来了当节点为空时返回0 。 好了至此循环的主体返回值边界条件都定义好了那么整个递归的代码是不是就水到渠成了。这样一看递归也没什么了不起的 ps:除了向下思考其实也可以向上思考比如还是遍历到了某个节点那么这个节点向上一层走是不是要有一个返回值呢那么返回值是什么呢是不是和自己原来需要的right(or left)相同只不过现在轮到自己了自己原来需要最大贡献那么此时返回时就返回最大贡献自己的最大贡献不就是node.valmax(left,right)。就像是老板一层一层的压榨员工一样。 看完这些我结合我的AI做了一个总结: 嗯,也是对这道题的一个交代吧
在递归类的题目中可能很多人都和我一样会感到困惑尤其是写递归的过程中常常遇到“会看不会写”的窘境。递归的本质看似简单但在实际应用中却往往让人抓不住重点。然而解答这类题目的关键在于理清递归的基本框架与思维路径而一旦掌握了这个过程递归将不再神秘。
递归的困境一看就会一写就废
在初学递归时我想大家都会有一种“知道大概但无从下手”的感觉。这是因为递归不同于其他常规的解题思路它往往需要我们站在一个较高的抽象层次去思考问题的整体而不是仅仅关注细节。尤其是递归中“自我调用”的特性让人很容易在一开始时就迷失在代码的具体实现中而忽略了逻辑上的整体构建。
解题的核心思路先明确递归的主体
要想解决递归类问题首先必须放下对代码细节的焦虑回到问题本身。一个清晰的递归思路通常可以归纳为几个关键点递归的主体是什么边界条件是什么返回值是什么这几个问题解决后递归的代码往往也就顺理成章了。
在这道题中我们的目标是找到一条路径的最大值。那么这里的递归主体可以这样定义我们在每个节点上求解“从当前节点出发经过该节点的最大路径值”而这一最大路径值是由当前节点的值加上它的左右子树的最大路径值之和来确定的。然而如果左右子树的某个最大路径值为负数显然它对我们整体路径的贡献是负的故我们应该舍弃这些负贡献而仅取正值部分。这其实隐含了一种贪心算法的思路在每次递归中我们只选择对整体有利的子路径而放弃那些对整体无益的部分。
递归的层次结构从上到下的自我调用
接下来我们需要思考左右子树的最大路径值如何求解。这其实就是递归的核心——我们将问题递归分解为更小的子问题通过不断地递归调用自身最终在叶子节点时触发递归的终止条件。在这道题中递归的终止条件非常自然当我们到达叶子节点的左右子树为空时最大路径值为0。通过这样的层层递归最后回溯时将每个节点的最大路径值传递回去形成了完整的递归过程。
递归的回溯每个节点的最大贡献
在递归过程中我们不仅向下遍历也需要向上回溯。在每次递归回溯时我们需要将当前节点的“最大贡献”值返回给它的上一级节点而这个最大贡献值正是当前节点的值加上左右子树中较大的那一部分。这就像是从员工到老板逐层递交成果老板需要下属的最大贡献而下属则将其最佳的工作结果汇报给老板。最终通过逐层回溯每一层都只保留了最佳的路径贡献从而得到了全局的最优解。
总结
递归的美妙之处在于它让问题的层次结构清晰明了。通过递归我们不仅可以将复杂的问题逐步拆解还能在边界条件明确的情况下逐步解决每一层次的子问题。而这种由内而外的层层递归、由下而上的逐步回溯使得递归问题不仅在形式上简洁优美也在逻辑上充满了挑战与成就感。写好递归的关键并不在于一开始就写出完整的代码而在于明确递归的主体理解问题的层次结构顺其自然地将边界条件、返回值、递归过程一一定义出来。这样一来递归问题自然就迎刃而解了。
