今日总结：
思考前序遍历+回溯，后序遍历的使用场景，与递归流程
平衡二叉树
题目链接：110. 平衡二叉树 - 力扣（LeetCode）
整体思路：
平衡二叉树是指：左右两棵子树的高度差小于1
二叉树的高度：
1、树中某个节点到其最远叶节点的路径长度
2、一般使用后序遍历，先计算左右子节点的高度，再计算当前节点的高度，实现从二叉树的下到上的顺序
3、在前几天的学习中，二叉树的最大深度，使用的是求根节点的高度，其实也可以使用前序遍历+回溯的方法
二叉树的深度：
1、树中某个节点到根节点的路径长度
2、一般使用前序遍历+回溯，先计算当前节点的深度，再计算子节点的深度，实现二叉树的上到下的顺序
这道题的思路:
与高度有关，所以使用后序遍历，
1、确定递归返回参数、传入参数
返回参数就是当前节点的高度，传入的就是当前节点
2、确定停止条件
当节点==nullptr
3、确定单层逻辑
1、后序遍历先计算左右子节点的高度；
2、然后判断左右子节点的高度是不是大于1，如果大于1说明底层就不是平衡，上层直接不需要判断了；如果小于等于1，获取当前节点的高度
3、需要设置一个标志位-1，当返回-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 digui(TreeNode* root)
{
//2、截止条件
if(root==nullptr)return 0;
//3、单层逻辑
//获取左右子树的深度
int left_depth = digui(root->left);
if(left_depth==-1)return -1;//规定返回-1表示这个二叉树已经从底部某层不是平衡二叉树
int right_depth =digui(root->right);
if(right_depth==-1)return -1;//规定返回-1表示这个二叉树已经从底部某层不是平衡二叉树
//判断左右子树的高度是不是大于1
if(abs(left_depth-right_depth)>1)return -1;//规定返回-1表示这个二叉树已经从底部某层不是平衡二叉树
//如果此时还是平衡，就返回当前节点的高度
return 1+max(left_depth,right_depth);
}
bool isBalanced(TreeNode* root) {
//平衡二叉树：左右子树的高度不超过1
//高度：当前节点到叶节点的层数
//深度：根节点到当前节点的最长边数（根1）
//高度使用后序遍历左右中
//深度使用前序遍历中左右（需要回溯）
//这道题判断左右子树的高度，所以使用后序遍历
int depth = digui(root);
if(depth ==-1)return false;
else return true;
}
};二叉树所有路径
题目链接：257. 二叉树的所有路径 - 力扣（LeetCode）
整体思路：
因为要获得二叉树的所有路径，所以从根节点出发->向下寻找路径->前序遍历+回溯
1、确定递归的返回参数、传入参数
返回参数：返回参数可以是路径，但是路径可以在找到完整的路径之后记录到vector<string>res中，所以不需要返回值
传入参数：当前节点、当前路径、记录路径的结果res
//1、确定递归的返回参数、传入参数
//返回的参数：在求路径，所以返回的应该是vector类型的路径，但是在递归中就将完成的路径记录了，无需返回参数。。
//传入的参数：当前的节点、在遍历一条路径后，将路径存储到vector的结果res中、当前节点所在的路径
void digui(TreeNode* root,vector<TreeNode*>&path,vector<string>&res)//将path填入结果res中要注意int转string，之所以使用int是便于记录，填入string其实也可以2、确定停止条件
一般的二叉树递归停止条件：cur==nullptr；就是需要返回了，比如在获取二叉树的最大深度的时候，return 0,但是，这是为了返回的时候确定叶子节点的层数是1而设置的；
在这道题中，路径到最后的叶子节点就停止了，所以不需要到cur==nullptr，而是cur->left==nullptr&&cur->right==nullptr 触发写入路径
//2、判断截止条件
//以往的递归截止条件（二叉树的最大深度等）条件是root==nullptr,return 0，因为最下一层返回0，上边的层才能通过0层计算高度
//这道题是寻找路径，最后只需要到叶子节点，到不了叶子节点的空左子节点和空右子节点
//当走到最后的叶子节点，需要将叶子节点也加入到路径中，再进行记录返回
if(root->left==nullptr&&root->right==nullptr)//此时路径应该已经完成，需要记录到res中将path的值填入到res中，但是path是int类型，res是string类型，需要使用to_string来进行转换（整型转换成字符串使用to_string;字符串转换成整型使用stoi）同时加上->符号
{
//记录当前最后一个叶子节点
path.push_back(root);
string s;
for(int i=0;i<path.size()-1;i++)
{
//使用将int转换成string的函数to_string
s += to_string(path[i]->val);
s +="->";
}
//最后一个不需要"->"
s +=to_string(path[path.size()-1]->val);
//将路径写入结果中
res.push_back(s);
return ;
}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:
//使用前序遍历+回溯的递归
//1、确定递归的返回参数、传入参数
//返回的参数：在求路径，所以返回的应该是vector类型的路径，但是在递归中就将完成的路径记录了，无需返回参数。。
//传入的参数：当前的节点、在遍历一条路径后，将路径存储到vector的结果res中、当前节点所在的路径
void digui(TreeNode* root,vector<TreeNode*>&path,vector<string>&res)//将path填入结果res中要注意int转string，之所以使用int是便于记录，填入string其实也可以
{
//2、判断截止条件
//以往的递归截止条件（二叉树的最大深度等）条件是root==nullptr,return 0，因为最下一层返回0，上边的层才能通过0层计算高度
//这道题是寻找路径，最后只需要到叶子节点，到不了叶子节点的空左子节点和空右子节点
//当走到最后的叶子节点，需要将叶子节点也加入到路径中，再进行记录返回
if(root->left==nullptr&&root->right==nullptr)//此时路径应该已经完成，需要记录到res中
{
//记录当前最后一个叶子节点
path.push_back(root);
string s;
for(int i=0;i<path.size()-1;i++)
{
//使用将int转换成string的函数to_string
s += to_string(path[i]->val);
s +="->";
}
//最后一个不需要"->"
s +=to_string(path[path.size()-1]->val);
//将路径写入结果中
res.push_back(s);
return ;
}
//3、确定单层递归
//记录当前节点
path.push_back(root);
//如果有左节点，需要左节点遍历
if(root->left!=nullptr)
{
digui(root->left,path,res);
//向上回溯一次，因为往下走了一次，导致path中多了一个数据，此时需要往右走，删除左子节点的数据
path.pop_back();
}
//如果有右节点，需要右节点遍历
if(root->right!=nullptr)
{
digui(root->right,path,res);
path.pop_back();
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<TreeNode*>path;
vector<string>res;
digui(root,path,res);
return res;
}
};左叶子之和
题目链接：404. 左叶子之和 - 力扣（LeetCode）
整体思路：
求的是左叶子之和，左叶子指的是：当前节点的左子节点是叶子节点的左子节点
可以使用递归来解题，但是因为是求的最下方的叶子节点，所以可以先求一个节点的左右节点的左叶子之和，再计算当前节点-->左右中，后序遍历；与求路径不同，路径是从上到下，记录当前节点->左子节点...前序遍历+递归；这道题是从下往上，后序遍历
1、确定递归的返回参数、输入参数
输入参数是节点，返回参数是当前节点的左叶子之和int
int digui(TreeNode* root)2、确定递归的停止条件：
递归从上往下，当遇到cur==nullptr，就返回0，表示当前节点（空）的左叶子之和为0
//2、确定递归的停止条件
//停止条件：遍历到nullptr
if(root==nullptr) return 0;//空节点的左叶子为03、确定单层递归的逻辑：
因为是后序遍历，需要先递归左子节点、再递归右子节点，判断当前位置是不是左叶子，最后将左子节点与右子节点的左叶子之和记录返回。
//3、确定递归的单层逻辑
//当找到左侧叶子的时候，记录当前的值
//递归左子节点
int left_sum = digui(root->left);
int right_sum = digui(root->right);
if(root!=nullptr&&root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr)//当前节点不为空，左子节点不为空，左子节点为叶子节点
{
left_sum =root->left->val;
}
int sum = left_sum + right_sum;
return sum;递归代码：
/**
* 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 digui(TreeNode* root)
{
//2、确定递归的停止条件
//停止条件：遍历到nullptr
if(root==nullptr) return 0;//空节点的左叶子为0
//3、确定递归的单层逻辑
//当找到左侧叶子的时候，记录当前的值
//递归左子节点
int left_sum = digui(root->left);
int right_sum = digui(root->right);
if(root!=nullptr&&root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr)//当前节点不为空，左子节点不为空，左子节点为叶子节点
{
left_sum =root->left->val;
}
int sum = left_sum + right_sum;
return sum;
}
int sumOfLeftLeaves(TreeNode* root) {
return digui(root);
}
};