https://blog.csdn.net/qq_43448818/article/details/127240033

一、递归三大部分

1、递归的参数和返回值
2、终止条件
3、单层递归逻辑

image.png

二、递归逻辑分两层，一个是递，另一部分是归

归是由终止条件和最后的return实现的

leftValue ＝ recursion(array,b1,c1) 

进入递归函数后，遇到终止条件，获得返回值后，将返回值给leftValue，退回本层

rightValue ＝ recursion(array,b2,c2)

进入递归函数后，遇到终止条件，获得返回值后，将返回值给rightValue，退回本层

最后利用函数最后的return 返回上一层递归

递 就是树分分叉实现，也就是左右节点的出现

三、递归函数的具体描述

递归的参数和返回值 这个看清楚返回值类型和参数类型就好

终止条件（只有遍历到最后的节点才会执行，负责将我们从最后一层脱离）

遍历到什么节点就结束我们的递归，不再继续往深层继续递归

if(root == NULL 或者是叶子节点)
     return  xxx

单层递归逻辑

可以先看成只有一层递归下怎么写

中节点（递归函数的核心）

也就是负责自顶向下的工作的操作 中节点的处理是我们实际要处理的逻辑，处理的地方，也就是改变的地方，最后会通过return 返回去影响中节点

后序遍历的时候就是通过return 将结果给我们的根节点

左、右节点（负责分叉处理） 我们可以想一下什么时候分叉处理

leftValue ＝ recursion(array,b1,c1) 
rightValue ＝ recursion(array,b2,c2)

自底向上的操作 我们递归都是先达到最深的地方，返回就靠这个return从本层跳到上一层 回到上一层 return

测试

反转二叉树

https://www.cnblogs.com/jay-huaxiao/p/13812701.html
解决递归问题一般就三步曲，分别是：

第一步，定义函数功能
第二步，寻找递归终止条件
第二步，递推函数的等价关系式

class Solution {
// 第1步：定义函数功能
    public TreeNode invertTree(TreeNode root) {
 // 第2步：寻找 终止条件
         if(root==null || (root.left ==null && root.right ==null)){
           return root;
         }

// 第3步： 递推函数的等价关系式

         //翻转左子树
         TreeNode left = invertTree(root.left);
         //翻转右子树
         TreeNode right= invertTree(root.right);
         //左右子树交换位置~
         root.left = right; //应该只关注当前这一级， 中节点 
         root.right = left;
         return root;
    }
}