110.平衡二叉树
因为这道题需要求高度，所以得用后序遍历。昨天有一道题是求最大深度的，可以用后序遍历做出来，但我没按那个方法写。就先做了求最大深度的题。理解的不够,以后还得再做一遍。
class Solution {
public:
int result;
void getDepth(TreeNode* cur,int dep){
if(result < dep){
result = dep;
}
if((cur->left == nullptr) && (cur->right == nullptr)){
return ;
}
if(cur->left != nullptr){
dep++;
getDepth(cur->left,dep);
dep--;
}
if(cur->right != nullptr){
dep++;
getDepth(cur->right,dep);
dep--;
}
return ;
}
int maxDepth(TreeNode* root) {
result = 0;
if(root == nullptr){
return result;
}
getDepth(root,1);
return result;
}
};
然后这道求是不是平衡二叉树的题还是不会做。照抄了一遍，意思是懂的，但是自己写不出来。
class Solution {
public:
int getHeight(TreeNode* cur){
if (cur == NULL) {
return 0;
}
int left_height = getHeight(cur->left);
if(left_height == -1){
return -1;
}
int right_height = getHeight(cur->right);
if(right_height == -1){
return -1;
}
int result;
if(abs(left_height-right_height)>1){
result = -1;
}
else{
result = 1+max(left_height,right_height);
}
return result;
}
bool isBalanced(TreeNode* root) {
if(!root){
return true;
}
else{
if(getHeight(root) == -1){
return false;
}
else{
return true;
}
}
return true;
}
};
257. 二叉树的所有路径
不会，崩溃了。。。。
404.左叶子之和
终于做出一道题了。而且这道题在之前学二叉树的时候做过，但是没独立做出来，但是这回写出来了。
class Solution {
public:
int sum;
void travesal(TreeNode* cur){
if(!cur){
return ;
}
if((cur->left) && (!cur->left->left) && (!cur->left->right)){
sum = sum + cur->left->val;
}
travesal(cur->left);
travesal(cur->right);
}
int sumOfLeftLeaves(TreeNode* root) {
sum = 0;
if(!root){
return sum;
}
travesal(root);
return sum;
}
};
