一入递归深似海，算法之美无止境

最近在刷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 = left+right+node,val，但是有一个前提，我们要求的是最大路径，所以若是left或者right小于等于0了，那么我们就没有必要把这些值加上了，因为加上一个负数，会使得最大路径变小。这里的最大路径中的最其实就是一个限定条件，也就是我们常说的贪心算法，只取最大，最好，其余的直接丢弃。

2、好了，1中的主体我们已经明确了，但是还存在一个问题，那就是left和right具体应该怎么求，也就是left和right的递归形式。显然我们要把node.left和node.right再次传输到递归函数中，重复上述的操作。但如果到达了叶子节点，是不是需要往上一层返回了呢？那么返回值又是多少呢？ 我们要明确left和right的基本含义，它们表示的是最大贡献，那么一个节点的最大贡献就等于node.val+max(left,right)，这个节点本身选上，然后从它的左右子树中选择最大的那个加上。 对于叶子节点也是这样，但是叶子节点的左右子树都为空，所以加上0，哎，注意看，此时是不是边界条件也出来了，当节点为空时，返回0 。 好了，至此循环的主体，返回值，边界条件都定义好了，那么整个递归的代码是不是就水到渠成了。这样一看递归也没什么了不起的！！！

ps:除了向下思考，其实也可以向上思考，比如还是遍历到了某个节点，那么这个节点向上一层走，是不是要有一个返回值呢，那么返回值是什么呢？是不是和自己原来需要的right(or left)相同，只不过现在轮到自己了，自己原来需要最大贡献，那么此时返回时就返回最大贡献，自己的最大贡献不就是node.val+max(left,right)。就像是老板一层一层的压榨员工一样。

看完这些我结合我的AI做了一个总结:  嗯,也是对这道题的一个交代吧

在递归类的题目中，可能很多人都和我一样会感到困惑，尤其是写递归的过程中常常遇到“会看不会写”的窘境。递归的本质看似简单，但在实际应用中却往往让人抓不住重点。然而，解答这类题目的关键在于理清递归的基本框架与思维路径，而一旦掌握了这个过程，递归将不再神秘。

递归的困境：一看就会，一写就废

在初学递归时，我想大家都会有一种“知道大概，但无从下手”的感觉。这是因为递归不同于其他常规的解题思路，它往往需要我们站在一个较高的抽象层次去思考问题的整体，而不是仅仅关注细节。尤其是递归中“自我调用”的特性，让人很容易在一开始时就迷失在代码的具体实现中，而忽略了逻辑上的整体构建。

解题的核心思路：先明确递归的主体

要想解决递归类问题，首先必须放下对代码细节的焦虑，回到问题本身。一个清晰的递归思路，通常可以归纳为几个关键点：递归的主体是什么？边界条件是什么？返回值是什么？这几个问题解决后，递归的代码往往也就顺理成章了。

在这道题中，我们的目标是找到一条路径的最大值。那么，这里的递归主体可以这样定义：我们在每个节点上求解“从当前节点出发，经过该节点的最大路径值”，而这一最大路径值是由当前节点的值加上它的左右子树的最大路径值之和来确定的。然而，如果左右子树的某个最大路径值为负数，显然它对我们整体路径的贡献是负的，故我们应该舍弃这些负贡献，而仅取正值部分。这其实隐含了一种贪心算法的思路：在每次递归中，我们只选择对整体有利的子路径，而放弃那些对整体无益的部分。

递归的层次结构：从上到下的自我调用

接下来，我们需要思考左右子树的最大路径值如何求解。这其实就是递归的核心——我们将问题递归分解为更小的子问题，通过不断地递归调用自身，最终在叶子节点时触发递归的终止条件。在这道题中，递归的终止条件非常自然：当我们到达叶子节点的左右子树为空时，最大路径值为0。通过这样的层层递归，最后回溯时将每个节点的最大路径值传递回去，形成了完整的递归过程。

递归的回溯：每个节点的最大贡献

在递归过程中，我们不仅向下遍历，也需要向上回溯。在每次递归回溯时，我们需要将当前节点的“最大贡献”值返回给它的上一级节点，而这个最大贡献值正是当前节点的值加上左右子树中较大的那一部分。这就像是从员工到老板逐层递交成果，老板需要下属的最大贡献，而下属则将其最佳的工作结果汇报给老板。最终，通过逐层回溯，每一层都只保留了最佳的路径贡献，从而得到了全局的最优解。

总结

递归的美妙之处在于它让问题的层次结构清晰明了。通过递归，我们不仅可以将复杂的问题逐步拆解，还能在边界条件明确的情况下逐步解决每一层次的子问题。而这种由内而外的层层递归、由下而上的逐步回溯，使得递归问题不仅在形式上简洁优美，也在逻辑上充满了挑战与成就感。写好递归的关键并不在于一开始就写出完整的代码，而在于明确递归的主体，理解问题的层次结构，顺其自然地将边界条件、返回值、递归过程一一定义出来。这样一来，递归问题自然就迎刃而解了。