leetcode解题启发递归

递归的定义&＃xff1a;直接或间接的调用自身称为递归

递归的特点&＃xff1a;本质是分而自治的思想&＃xff0c;顾名思义&＃xff0c;递和归。递是传递、归是回归&＃xff0c;所以递归满足一下的两点&＃xff1a;

• 递、继续调用
• 归、收敛条件

递归的思路&＃xff1a;

• 将原问题分解为规模较小的问题进行处理&＃xff08; 分解后的问题与原问题完全相同&＃xff0c;但规模较小&＃xff09;
• 设置收敛条件&＃xff08;递归未到达边界时&＃xff0c;继续递归&＃xff0c;到达边界条件时&＃xff0c;递归结束&＃xff09;

这里通过一个简单的例子直观感受下&＃xff0c;leetcode617.合并二叉树

题目描述&＃xff1a;

给定两个二叉树&＃xff0c;想象当你将它们中的一个覆盖到另一个上时&＃xff0c;两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠&＃xff0c;那么将他们的值相加作为节点合并后的新值&＃xff0c;否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出:
合并后的树:3/ \4 5/ \ \ 5 4 7


根据分而治之的思想&＃xff0c;我们可以这样去思考&＃xff1a;

• 根节点1和根节点2合并处理
• 把左节点看成新的根节点&＃xff0c;根节点1和根节点2合并处理
• … 直至二叉树的最后一层
• 把右节点看成新的根节点&＃xff0c;根节点1和根节点2合并处理
• … 直至二叉树的最后一层

上述的思路步骤&＃xff0c;也就是大问题可以由多个小问题分开解决&＃xff0c;这就为递归解决提供了可能&＃xff0c;代码如下&＃xff1a;

public class Solution {public TreeNode merge(TreeNode t1, TreeNode t2) {//收敛条件&＃xff1a; 某个二叉树到达最后一层if (t1 &＃61;&＃61; null || t2 &＃61;&＃61; null) {return t1 !&＃61; null ? t1 : t2;}//根节点相加t1.val &＃43;&＃61; t2.val;//根据左右子树分开递归调用t1.left &＃61; merge(t1.left, t2.left);t1.right &＃61; merge(t1.right, t2.right);return t1;}
}


相应的题型&＃xff0c;以下leetcode题目的求解思路跟上边的一样&＃xff1a;

• 101.对称二叉树
• 104.二叉树的最大深度
• 105.从前序遍历和中序遍历序列构造二叉树
• 114.二叉树展开为链表

当然leetcode一些题目中所用的递归思路是更复杂的&＃xff0c;像字符串操作、斐波那契数列、链表操作等等都有应用&＃xff0c;但是递归的本质是相同的&＃xff0c;是在简单递归的外层&＃xff0c;加了诸多条件限制。