算法第13天|继续学习二叉树：平衡二叉树（递归）、二叉树所有路径（递归）、左叶子之和（递归）
今日总结：
思考前序遍历+回溯，后序遍历的使用场景，与递归流程
平衡二叉树
题目链接：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表示这个二叉树已经从底部某层不是平衡二叉树//判断左右子树的高度是不是大于1if(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_strings += 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_strings += 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、确定递归的停止条件//停止条件：遍历到nullptrif(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、确定递归的停止条件//停止条件：遍历到nullptrif(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);}
};