day 15|110.平衡二叉树 **257. 二叉树的所有路径 ** 404.左叶子之和 222.完全二叉树的节点个数
110.平衡二叉树
110.平衡二叉树 | 代码随想录
笔记
求高度用后续遍历，求深度用前序遍历
实操出现问题
代码/比较
class Solution {
public:int height_func(TreeNode* root){//截至条件if(root==nullptr) return 0;//单层递归逻辑：后序遍历，在节点处返回最大值+1，如果左右树高度差值大于1，返回-1，如果左右树任何一个返回-1，也向上返回-1int leftheight=height_func(root->left);if(leftheight==-1) return -1;int rightheight=height_func(root->right);if(rightheight==-1) return -1;if(abs(rightheight-leftheight)>1) return -1;else return(max(leftheight,rightheight)+1);}bool isBalanced(TreeNode* root) {int result=height_func(root);return (result==-1) ? false:true;}
};
257. 二叉树的所有路径
笔记：
前序遍历，因为是先节点再往左右子树遍历
设计回溯，因为需要先把结尾处的元素弹出再进行下一个结果的处理。
实操出现的问题：
一定要注意当前递归的返回值。
代码/比较：
class Solution {
public:void tranverse(TreeNode* root,vector<int>& _before,vector<string>& result)//result用来存储最终返回值，_before用来存储int类型的路径{//中节点,为了避免把叶子节点忽略掉，应该放在这里_before.push_back(root->val);//截至条件：碰到叶子节点，讲当前的路径变成string类型,放到result中if(root->left==nullptr&&root->right==nullptr) {string path;//路径转换为题解要求path=to_string(_before[0]);//先把第一个数放进string里面for(int i=1;i<_before.size();i++){path=path+"->"+to_string(_before[i]);}result.push_back(path);return;}//单层递归的逻辑：前序遍历，在左右子节点都要回溯一次，把当前_before中弹出最后一个数;中节点处把元素push入_before//左节点if(root->left) {tranverse(root->left,_before,result);_before.pop_back();//把最后一个数弹出}//右节点if(root->right) {tranverse(root->right,_before,result);_before.pop_back();//把最后一个数弹出}return;}vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> _before;tranverse(root,_before,result);return result;}
};
精简代码：
class Solution {
private:void traversal(TreeNode* cur, string path, vector<string>& result) {path += to_string(cur->val); // 中if (cur->left == NULL && cur->right == NULL) {result.push_back(path);return;}if (cur->left) traversal(cur->left, path + "->", result); // 左if (cur->right) traversal(cur->right, path + "->", result); // 右}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;string path;if (root == NULL) return result;traversal(root, path, result);return result;}
};
回溯就隐藏在traversal(cur->left, path + "->", result);中的 path + "->"。 每次函数调用完，path依然是没有加上"->" 的，这就是回溯了。
404.左叶子之和
笔记：
使用后序遍历：左右中，先统计左右子树的左叶子之和，在节点处统计这个树的总和
1.递归函数的返回值和传入参数：传入根节点，返回总和int
2.停止条件：碰到nullptr，返回0；碰到叶子节点，返回0；
3.递归的单层逻辑：左右节点递归得到左叶子之和，遍历左边节点时判断是否为叶子节点，如果是则相加
使用前序遍历：中左右：先在中节点处判断是否为左叶子，如果是，则统计数据；依次遍历左右子树
1.递归函数的返回值和传入参数： 无返回值，传入根节点和bool型变量，该变量表示该节点是否为左孩子？
2.停止条件：碰到nullptr，返回0；
3.递归的单层逻辑：如果是左孩子并且是叶子节点则统计val值；再依次遍历左、右子树
实操出现问题：
为什么判断左叶子的if语句在遍历左子树之后？没搞懂
代码/比较：
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {//截至条件：if(root==nullptr) return 0;if(root->left==nullptr&&root->right==nullptr) return 0;//单层递归逻辑：int left_sum=sumOfLeftLeaves(root->left);if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况left_sum = root->left->val;}int right_sum=sumOfLeftLeaves(root->right);int sum=left_sum+right_sum;return sum;}
};
如果用前序遍历更好理解：
class Solution {
public:int sum=0;//左叶子总和void preorder_leafsum(TreeNode* root,bool isleft){//截止条件：if(root==nullptr) return;//单层递归逻辑：前序遍历：中：如果是左孩子、还是叶子节点，说明是左叶子，计入数据；左右：依次递归即可if((isleft==true)&&(root->left==nullptr)&&(root->left==nullptr))sum+=root->val;preorder_leafsum(root->left,true);preorder_leafsum(root->right,false);}int sumOfLeftLeaves(TreeNode* root) {preorder_leafsum(root,false);return sum;}
};
222.完全二叉树的节点个数
笔记：
题目就是让找最大深度的最靠左边的节点。
由于是从左向右遍历，所以只记录同一个深度下遇到的第一个叶子节点，如果深度更大则更新这个值。
左右子树的更新：向下一层递归的时候应该把深度+1，但是递归完成后应该-1，因为还需要继续遍历其他值
1.递归传入数据和输出参数：传入当前最大深度、传入节点root。 输出参数：无。（因为直接操纵全局变量）
2.递归截止条件：如果碰到叶子节点，进行如下判断：最大深度是否比现有的深度大？如果是，则更改全局变量，如果不是则不予修改。return即可；
3.单层递归的逻辑：继续遍历左右子树，应当是先左后右；注意递归中传入的最大深度参数应该加一，但是当前层的最大深度不变；
代码：
class Solution {
public:int result;//记录最左边的节点值int maxepth=INT32_MIN;//最大深度void find_leftmax(TreeNode* root,int depth){//截止条件：如果碰到叶子节点，进行如下判断：最大深度是否比现有的深度大？如果是，则更改全局变量，如果不是则不予修改。return即可；if(root->left==nullptr&&root->right==nullptr) {if(depth>maxepth){maxepth=depth;result=root->val;}return;} //单层递归的逻辑：if(root->left)find_leftmax(root->left,depth+1);if(root->right)find_leftmax(root->right,depth+1);return ;}int findBottomLeftValue(TreeNode* root) {find_leftmax(root,0);return result;}
};
1