今日总结：
递归法的三段式应用
1、确定递归的返回参数、输入参数
2、确定递归的停止条件
3、确定单次递归的递归逻辑与返回值
对称二叉树需要重新思考
1、迭代法中是如何使用队列进行判断对称的
2、递归法中是传入什么参数，什么逻辑判断对称的
二叉树的最小深度需要重新思考：
所谓的深度是指根节点到叶子节点，如果某个节点只有左子节点或者右子节点，不是最短的路径，只有左右子节点都没有的时候才是底。
翻转二叉树
题目链接：226. 翻转二叉树 - 力扣（LeetCode）
整体思路：
翻转二叉树，本质上可以看作是对左右子树的翻转，所以更加细的讲：将每个节点的左右子节点进行翻转就实现了翻转二叉树。
对于深度优先搜索：
前序遍历（中前后）（递归、迭代）
后序遍历（前后中）（递归、迭代）
对于广度优先搜索：
层序遍历（递归、迭代）
都是可以使用的，在要将当前位置节点记录的时候转换左右节点就实现了翻转二叉树。
前序遍历递归翻转二叉树代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
//前序遍历
void digui(TreeNode* &root)
{
//判断停止条件
if(root==nullptr)return;
swap(root->left,root->right);
digui(root->left);
digui(root->right);
}
TreeNode* invertTree(TreeNode* root) {
//深度优先、前序遍历翻转
digui(root);
return root;
}
};前序遍历迭代翻转二叉树代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
深度优先、前序遍历迭代法
stack<TreeNode*>stk;
//根节点入栈
if(root==nullptr)return root;
stk.push(root);
while(!stk.empty())
{
//出栈
TreeNode*cur = stk.top();
stk.pop();
swap(cur->left,cur->right);
//右左节点入栈
if(cur->right!=nullptr)stk.push(cur->right);
if(cur->left!=nullptr)stk.push(cur->left);
}
return root;
}
};
层序遍历递归翻转二叉树代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>>res;
void digui(TreeNode* &root,int depth)
{
//停止条件
if(root==nullptr)return ;
//判断是不是第一次进入这一行
if(res.size()==depth)res.push_back(vector<int>());
res[depth].push_back(root->val);
//交换左右子节点
swap(root->left,root->right);
if(root->left!=nullptr) digui(root->left,depth+1);
if(root->right!=nullptr) digui(root->right,depth+1);
//递归左，递归右
}
TreeNode* invertTree(TreeNode* root) {
//使用广度优先，层序遍历，递归法
//定义一个存储节点的vector数组，因为要跟depth比较
digui(root,0);
return root;
}
};层序遍历迭代翻转二叉树代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
//使用广度优先、层序遍历迭代法
//定义队列
queue <TreeNode*>que;
if(root==nullptr)return root;
que.push(root);
//开始while判断
while(!que.empty())
{
//记录队列的长度，因为队列一直变换
int size = que.size();
for(int i=0;i<size;i++)
{
//弹出队头
TreeNode* cur = que.front();
que.pop();
swap(cur->left,cur->right);
if(cur->left!=nullptr) que.push(cur->left);
if(cur->right!=nullptr)que.push(cur->right);
}
}
return root;
}
};对称二叉树
题目链接：101. 对称二叉树 - 力扣（LeetCode）
整体思路：
因为是寻找对称，是左边与右边的关系，可以看作是两棵子树的关系，可以通过对左右两棵子树的对应位置进行判断：使用递归、迭代（两个对应节点一组入栈或队）
递归法：
1、确定返回参数、传入的参数
这个题是判断是不是对称，返回参数是bool；
这个题是判断左右子树是不是对称，传入参数是两个节点
bool digui(TreeNode* left,TreeNode* right)2、确定停止条件
因为是判断是不是对称，当出现不对称或者遍历完了就返回
左边空，右边不空，返回false
左边不空，右边空，返回false
左边空，右边空，返回true
左边不空，右边不空，左边值不等于右边值，返回false
if(left==nullptr&&right!=nullptr) return false;
else if(left!=nullptr&&right==nullptr) return false;
else if(left!=nullptr&&right!=nullptr&&left->val!=right->val)return false;
else if(left==nullptr&&right ==nullptr)return true;3、确定单次递归的逻辑
获取下一次递归返回的bool值进行判断当前层次返回值
（1）将左节点的左节点与右节点的右节点继续递归
（2）将左节点的右节点与右节点的左节点继续递归
（3）两者的返回值都是true，当前层的返回值才能是true;
递归法代码
// /**
// * Definition for a binary tree node.
// * struct TreeNode {
// * int val;
// * TreeNode *left;
// * TreeNode *right;
// * TreeNode() : val(0), left(nullptr), right(nullptr) {}
// * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
class Solution {
public:
//递归返回的参数是布尔,传入的参数是需要判断的对称位置
bool digui(TreeNode* left,TreeNode* right)
{
//设置停止条件
//如果左空右不空、左不空右空、左右都不空但是值不同、左右都空
if(left==nullptr&&right!=nullptr) return false;
else if(left!=nullptr&&right==nullptr) return false;
else if(left!=nullptr&&right!=nullptr&&left->val!=right->val)return false;
else if(left==nullptr&&right ==nullptr)return true;
//只剩下左右都不空左右值相同
//左右两个节点都有自己的左右节点，所以是左节点的左子节点与右节点的右子节点；左节点的右子节点与右节点的左子节点进行判断
bool A = digui(left->left,right->right);
bool B = digui(left->right, right->left);
bool C =false;
return C= A&&B;
}
bool isSymmetric(TreeNode* root) {
//轴对称、首先判断左子节点与右子节点，之后判断的是左子节点的左子节点与右子节点的右子节点
//使用一个递归形式，将整个二叉树分为左子树与右子树
if(root==nullptr)return true;
return digui(root->left, root->right);
迭代法：
迭代法类似于层序遍历，但是与层序遍历不同；
（1）设置一个队列，用于存储左右子树的对应节点，
（2）每次取出对应的两个节点，用于判断当前两个节点是不是相同（对称）
（3）之后将两个节点的对应子节点入队，直到队空
迭代法代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
//使用类似层序遍历，队列
//将一层的节点输入进队列，两个两个的拿出，然后将其子节点输入到队列，直到队列为空
queue <TreeNode*> que;
if(root==nullptr)return true;
//将根节点的左右子节点输入到队列
que.push(root->left);
que.push(root->right);
while(!que.empty())
{
//进行判断两个节点的关系，出队
TreeNode* cur1 = que.front();
que.pop();
TreeNode* cur2 =que.front();
que.pop();
if(cur1==nullptr&&cur2!=nullptr)return false;
else if(cur1!=nullptr&&cur2==nullptr)return false;
else if(cur1==nullptr&&cur2==nullptr) continue;//不能直接返回true，因为跟递归不同，返回true不是返回上一层，而是直接返回答案，应该用continue直到队列是空的
else if(cur1!=nullptr&&cur2!=nullptr&&cur1->val!=cur2->val)return false;
//此时只有两个节点不空、节点一样
//队列中加入两个节点的对应位置的子节点
que.push(cur1->left);
que.push(cur2->right);
que.push(cur1->right);
que.push(cur2->left);
}
return true;
}
};二叉树的最大深度
整体思路
二叉树的深度，就是根节点到叶子节点的最远距离，可以使用递归的形式，从最下边开始计算节点的高度，直到根节点；也可以使用迭代法层序遍历直接判断有多少层
递归法
1、确定递归返回参数、输入参数
递归的返回参数应该是当前节点的高度，输入参数应该是当前节点
2、确定递归停止条件
当节点与到nullptr表示找到了叶子节点的下一个子节点，所以此层的高度应该是0
3、确定单层递归的递归逻辑
一个节点有左右子节点，当前节点返回：获取左右子节点的最大高度后+1
递归法代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
//1、确定递归返回参数、输入参数
//返回参数应该是高度，输入的参数应该是节点
int getdepth(TreeNode*root)
{
//2、确定停止条件
//当前节点是nullptr的时候就返回，返回的是高度0,假设叶子节点是高度1
if(root==nullptr)return 0;
//3、确定单层循环的循环逻辑
//获取左右子节点的高度，返回高的那个
int depth_left = getdepth(root->left);
int depth_right =getdepth(root->right);
return 1+max(depth_left,depth_right);
}
int maxDepth(TreeNode* root) {
//使用递归的方法，进行寻找depth
int depth = getdepth(root);
return depth;
}
};迭代法：
层序遍历迭代法模板
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
//定义一个深度
int depth=0;
//定义一个队列
queue <TreeNode*>que;
//根节点
if(root==nullptr)return 0;
que.push(root);
while(!que.empty())
{
//获取队列大小
int size = que.size();
for(int i=0;i<size;i++)
{
//临时节点，出队
TreeNode* cur = que.front();
que.pop();
if(cur->left!=nullptr) que.push(cur->left);
if(cur->right!=nullptr) que.push(cur->right);
}
depth++;
}
return depth;
}
};二叉树的最小深度
题目链接：111. 二叉树的最小深度 - 力扣（LeetCode）
整体思路：
与二叉树的最大深度类似，但是不能直接修改为min，因为所谓的最小深度，是从叶子节点到根节点，如果一个节点只有一个子节点，不属于叶子节点：
此时的最小深度应该需要是从拥有的子节点的那条路径进行往下，所以需要在最大深度的代码上添加限制条件：出现一个子节点的时候要如何？
递归法：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
//1、确定递归的返回、输入
int getdepth(TreeNode* root)
{
//2、确定递归的停止
if(root==nullptr)return 0;//最后的高度为0
//3、确定单层的逻辑及返回值
//如果当前节点的左右子节点不全，不能直接获取最小的depth，,而是让另一个不为nullptr的节点继续遍历，获取他的高度，只有叶子节点才能是底层的高度1
int left_depth = getdepth(root->left);
int right_depth = getdepth(root->right);
if(root->left==nullptr&&root->right!=nullptr)
return 1+right_depth;
if(root->left!=nullptr&&root->right==nullptr)
return 1+left_depth;
int depth = 1+min(left_depth,right_depth);
return depth;
}
int minDepth(TreeNode* root) {
return getdepth(root);
}
};迭代法：
迭代法就是在层序遍历迭代法的模板上，添加限制条件：寻找最先遇到的叶节点（左右子节点都没有）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
//层序遍历迭代法：
//定义队列,深度
queue<TreeNode*>que;
int depth=0;
//根节点入队
if(root==nullptr)return 0;
que.push(root);
while(!que.empty())
{
//定义队列大小
int size = que.size();
depth++;
for(int i=0;i<size;i++)
{
TreeNode* cur = que.front();
que.pop();
//如果当前节点没有子节点，就可以直接返回深度了
if(cur->left==nullptr&&cur->right==nullptr)return depth;
if(cur->left!=nullptr) que.push(cur->left);
if(cur->right!=nullptr) que.push(cur->right);
}
}
return depth;
}
};
// /**
// * Definition for a binary tree node.
// * struct TreeNode {
// * int val;
// * TreeNode *left;
// * TreeNode *right;
// * TreeNode() : val(0), left(nullptr), right(nullptr) {}
// * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
// class Solution {
// public:
// //1、确定递归的返回、输入
// int getdepth(TreeNode* root)
// {
// //2、确定递归的停止
// if(root==nullptr)return 0;//最后的高度为0
// //3、确定单层的逻辑及返回值
// //如果当前节点的左右子节点不全，不能直接获取最小的depth，,而是让另一个不为nullptr的节点继续遍历，获取他的高度，只有叶子节点才能是底层的高度1
// int left_depth = getdepth(root->left);
// int right_depth = getdepth(root->right);
// if(root->left==nullptr&&root->right!=nullptr)
// return 1+right_depth;
// if(root->left!=nullptr&&root->right==nullptr)
// return 1+left_depth;
// int depth = 1+min(left_depth,right_depth);
// return depth;
// }
// int minDepth(TreeNode* root) {
// return getdepth(root);
// }
// };