递归算法：即一个程序反复调用自身的算法。
以一个经典阶乘为例，我们都知道阶乘
n! = n * (n-1)!
(n-1)! = (n-1) * (n-1)!
...
...
直到0！= 1 是我们都知道的，也就是终止条件。
所以我们可以写出代码：
class Jiecheng{
public static int jc(int n) {
if(n ==0) return 1;
return n* jc(n-1);
}
}
可以看到通过在jc()方法内部反复调用自身，直到n = 0的时候返回1,反推回去，例如n = 3的时候，
jc(3) = 3*jc(2)
jc(2) = 2*jc(1)
jc(1) = 1*jc(0)
当jc(0) 返回1了。所以可知:
jc(1) = 1*1 = 1
jc(2) = 2*jc(1) = 2
jc(3) = 3*jc(2) = 6
这就是递归算法，下面我结合LeetCode题库的递归算法做一个简单的分析。
LeetCode题库1137 第 N 个泰波那契数
image.png
分析一下：当n = 0,1,2的时候，找一下规律
#n = 0
T3 = T0 + T1 + T2
#n = 1
T4 = T1 + T2 + T3
#n = 2
T5 = T2 + T3 + T4
由上边的分析可得到Tn = T(n-3) + T(n-2) + T(n-1) 又根据T0，T1，T2的值都是已知的，这就是递归的结束条件
class Solution {
public long tribonacci(int n){
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
return long(tribonacci(n-1)) + long(tribonacci(n-2)) + long(tribonacci(n-3));
}
}
LeetCode题库 938. 二叉搜索树的范围和、
image.png
这道题目乍一看，根本看不懂，于是直接去看了解释，如下图，就是求满足7<=x<=15的x数的和。
image.png
首先根据这个二叉树进行递归终止条件的分析：(假设root为当前节点)
- root为null的时候返回0
- 当前节点root < L 的时候只需要对他的右子树进行递归
- 当前节点root > R的时候只需要对他的左子树进行递归
- 当前节点 L <= root <=R 的时候，因为当前节点满足条件，所以应该用当前节点root + 左子树递归 + 右子树递归
如果还是觉得难理解，那我们结合实际节点进行分析，假如节点5进行递归，因为5不在7和15之间，所以只需要对5的右子树进行再次递归，因为5的左子树肯定小于5，肯定不满足条件；
然后分析7,10,15这三个属于满足7和15之间的条件，所以返回root + 左递归的和 + 右递归的和
18相对于5节点，对18节点来说，只需要对左子树进行递归求和就可以了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rangeSumBST(TreeNode root, int L, int R) {
if(root == null) return 0;
if(root.val < L) return rangeSumBST(root.right, L, R);
if(root.val > R) return rangeSumBST(root.left, L, R);
return root.val + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R);
}
}
这里给出另一种解题思路：
先递归二叉树的节点，把节点从小到大装进List里面，然后遍历list取7到15之间的值。
class Solution {
List<Integer> list = new ArrayList<>();
int sum = 0;
public int rangeSumBST(TreeNode root, int L, int R) {
order(root);
for(Integer i : list){
if(i>=L && i<=R){
sum+=i;
}
}
return sum;
}
public void order(TreeNode root) {
if(root == null) return;
order(root.left);
list.add(root.val);
order(root.right);
}
}
LeetCode题库 687.最长同值路径
image.png
这题题面意思很容易理解，但是代码不是很好理解。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//记录最长路径
int sum = 0;
public int longestUnivaluePath(TreeNode root) {
jisuan(root);
return sum;
}
public int jisuan(TreeNode root) {
if(root == null) return 0;
int left = jisuan(root.left);
int right = jisuan(root.right);
left = (root.left != null && root.left.val == root.val) ? left + 1 : 0;
right = (root.right !=null && root.right.val == root.val) ? right + 1 : 0;
sum = Math.max(sum, left + right);
return Math.max(left, right);
}
}
以这个二叉树为例进行分析
image.png
解释：jisuan()这个递归方法把二叉树拆分到先分析最左边的辈分最小的二叉树；
image.png
并返回一个int值，这个值是left或者right中取最大值，因为我们拆分到最小单位了，所以如上图红框中所示4节点的左孩子是4相同则left = left + 1 = 1，右孩子也是4所以right = right + 1 = 1;这个最小单位二叉树构成的最长路径为2，sum = 1 + 1 = 2;但是注意这个jisuan()方法的返回值必须是左孩子或右孩子最长的那一个值，这里都是1所以返回1；
在分析右孩子最小辈分的如下图所示的二叉树；
image.png
直接分析5的右孩子5相同则right = 1；sum 总是取最大值，前边已经取2了，这里经对比还是2；jisuan()返回1；
最后分析1这个节点如下图所示：
image.png
left = 1;
right = 1;
但是当分析1和4的时候因为不相同，所以left = 0;分析1和5的时候因为不相同所以right = 0;
所以jisuan()返回0，sum还是取sum = 2和left + right = 0中的最大值，sum = 2;
因为sum一直是全局变量，一直在更新成最大的路径数，最终本题目返回sum = 2；
结合代码你就细品吧，确实是这么回事！！！
网友评论