前言

数据结构中的二叉树，是由n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

这是一种典型的非线性结构，所以对于这种结构的遍历，通常有两种方式，即广度优先探索和深度优先探索，而本章主要讲的就是这个深度优先探索，听起来挺高大上，其实就是所谓的递归。

递归思想

递归就是在运行的过程中调用自己。斐波那契数列就是典型的例子；即这样一个数列：1，1，2，3，5，8，13，21…从第三个数开始，每个数是前两个数之和。
那么我们想求第n项的值是多少就可以利用递归思想来解决问题。

int f(int n){
//结束条件
	if(n<=2){
	return 1;
	}
	//关系式
	return f(n-1)+f(n-2);
	}

通过判断终止条件，先不断传递函数，再通过return一个一个进行归还到最初的函数，得到最终结果。
所以要用递归，需要弄好三要素：
1、先判断能否用递归，即需不需要传递函数再通过返回的方式来解决问题。
2、如果可以，需要列出终止条件。
3、最后找出递归关系式即可。

例题

NO.1

先说一个二叉树的遍历例题

前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树。在访问左子树或者右子树的时候，左子树或者右子树又可以充当根结点这个角色，有自己的左子树和右子树，所以通过递归思想来完成遍历。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void preorder(struct TreeNode* root,int* res,int* resSize)
 {
 	//终止条件
     if(root == NULL)
    {
        return ;
    }
    //递归关系式
    res[(*resSize)++]=root->val;
    preorder(root->left,res,resSize);
    preorder(root->right,res,resSize);

 }
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* res=(int*)malloc(sizeof(int)*200);
    *returnSize=0;
    preorder(root,res,returnSize);
   
    return res;
}

如果上面看得比较复杂（由于力扣接口返回问题），那么通过打印的方式来演示

void BinaryTreePreOrder(BinaryTree* root)
{
	//终止条件
    if(root==NULL)
    {
        return ;
    }
    printf("%c ",root->val);
    //递归关系式
    BinaryTreePreOrder(root->left);
    BinaryTreePreOrder(root->right);

}

这是二叉树的深度优先探索的遍历方式，通过这种思路，来解决下面一些问题。

NO.2

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root){
   //终止条件
    if(root==NULL)
    {
        return 0;
    }
    //递归探身加对比长度，加上本身1；
    return fmax(maxDepth(root->right),maxDepth(root->left))+1;
}

解题思路

   对于递归思想，我们要从简单的看起，如图所示，我们一眼能看出深度为3，
我们先只考虑3这个根节点，可以先想一下终止条件是什么，即什么时候停止深
度计算。接着想左子树小于右子树，怎么只想要右子树而已。通过思考，我们
知道遇到空就停止，图所示左子树深度为1，右子树为2，那么可以通过比较来
长度来选择右子树，最后再加上根节点本身1即可。简单的考虑清楚了，一般来
说就解决%90的问题了，剩下的  就是一些特殊情况，没有考虑周到。

NO.3

解题思路

  对于该题目，一眼上去就是两边是镜像对称的，那么如果一指针在遍历，通
  过镜像也有一指针在遍历，两个指针遍历相同的话，不就轴对称了吗。
  所以我们可以创建两个指针来同时遍历。但又发现原函数不允许含有两个参
  数
  bool isSymmetric(struct TreeNode* root){
return FisSymmetric(root->left,root->right);
}
那我们就自己重新创立一个函数来递归遍历。
当然需要注意：左边指针遍历时，右边指针遍历是相反对称的。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 bool FisSymmetric(struct TreeNode* L,struct TreeNode* R)
 {
     //终止成功条件
     if(L==NULL&&R==NULL)
     {
         return true;
     }
     //判断条件（都不为空）
     if(L!=NULL&&R!=NULL)
     {
         //失败条件
         if(L->val!=R->val)
         {
            return false;
         }

         else
         {
             return FisSymmetric(L->left,R->right)&&FisSymmetric(L->right,R->left);
         }
     }
     //判断条件（一边为空）
     return false;
 }

bool isSymmetric(struct TreeNode* root){
return FisSymmetric(root->left,root->right);
}

通过代码可以看出，当判断出null或者镜像的两个数不相等时，其实就成功or失败了。所以我们就将这个结果传递给最初函数即可。直接return+递归函数即可。

return FisSymmetric(L->left,R->right)&&FisSymmetric(L->right,R->left);

NO.4

解题思路

  这道题一看好像与上一道题一样，但要考虑清楚，这是翻转，不能使用两个
  指针来解决(可能就只有我一开始这样做吧，嘻嘻)，通过仔细观察，这道题就
  是通过左右子树交换完成的，

 对于越多层来说，就是想通过最近根节点进行交换，再通过更大的根节点
 来交换，所以我们可以通过递归方法进行交换。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
*/


struct TreeNode* invertTree(struct TreeNode* root){
   //停止条件
    if(root==NULL)
    {
        return NULL;
    }
    //递归左子树和右子树，实行交换
     struct TreeNode* left=invertTree(root->left);
     struct TreeNode* right=invertTree(root->right);
     root->left=right;
     root->right=left;
   //返回
  return root;
   

NO.5

解题思路

  如果你对于前面几道题都理解透彻的话，那么这道题是非常容易的。根据题目
  很容易知道，叶子节点就是终点，也就是结束的最后一个，那么我们只需要判
  断每条路径之和是否与targenum匹配即可。当然，由于是判断子节点，所以
  需要先判断根节点是否为空。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool hasPathSum(struct TreeNode* root, int targetSum){
   //特殊条件
    if(root==NULL)
    {
        return false;
    }
    //终止条件
   if(root->left==NULL&&root->right==NULL)
   {
       return targetSum==root->val;

   }
   //递归探深
   return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
}

由于这里每个都要进行匹配，所以用或者来进行递归。

总结

总之，递归要想明白，要传递什么，return回什么，这是最关键的。终止条件要放在函数的前头，确认好关系式。在头脑中要有递归的思想类型图(就是开头的第二张照片)，而增强递归的理解，最好的方式就是多刷题，了解不同类型的递归方式。
最后，这些都是我做题过程中的理解，如果你有不同见解思路，欢迎下方评论，谢谢大家的观看。