一、递归三大部分

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;
    }
}