前言
数据结构中的二叉树，是由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回什么，这是最关键的。终止条件要放在函数的前头，确认好关系式。在头脑中要有递归的思想类型图(就是开头的第二张照片)，而增强递归的理解，最好的方式就是多刷题，了解不同类型的递归方式。
最后，这些都是我做题过程中的理解，如果你有不同见解思路，欢迎下方评论，谢谢大家的观看。
