110.平衡二叉树
文章链接:https://programmercarl.com/0110.平衡二叉树.html#题外话
题目链接:https://leetcode.cn/problems/balanced-binary-tree/description/
class Solution {
public:
//每次都要比较左右子树的高度差是否在1以内,所以递归是要统计子树的高度的
int getHeight(TreeNode* root){
if(root==NULL) return 0;
//获得左子树的高度,如果左子树高度为-1,说明已经失败了
int leftHeight=getHeight(root->left);
if(leftHeight==-1) return -1;
//获得右子树的高度,如果右子树高度为-1,说明已经失败了
int rightHeight=getHeight(root->right);
if(rightHeight==-1) return -1;
//如果左右子树的高度都不为-1,说明可以进行高度差的比较,判断是否在1以内
if(abs(leftHeight-rightHeight)>1) return -1;
//如果以上失败条件都能排除,则可以返回父节点的高度
return 1+max(leftHeight,rightHeight);
}
bool isBalanced(TreeNode* root) {
if(getHeight(root)==-1) return false;
return true;
}
};
257. 二叉树的所有路径
文章链接:https://programmercarl.com/0257.二叉树的所有路径.html
题目链接:https://leetcode.cn/problems/binary-tree-paths/description/
class Solution {
void traversal(TreeNode* node,string path,vector<string>&result){
//这里一开始要加上叶子节点
path+=to_string(node->val);
//再处理叶子节点的情况
if(node->right==NULL&&node->left==NULL){
result.push_back(path);
return;
}
//左
if(node->left) traversal(node->left,path+"->",result);
//右
if(node->right) traversal(node->right,path+"->",result);
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if(root==NULL) return {};
traversal(root,path,result);
return result;
}
};
404.左叶子之和
文章链接:https://programmercarl.com/0404.左叶子之和.html
题目链接:https://leetcode.cn/problems/sum-of-left-leaves/description/
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root==NULL) return 0;
int leftNum=0;
//不断向下遍历,直到遇到符合条件的(左孩子为叶子节点)左叶子节点和的值才会增加
if(root->left!=NULL&&root->left->left==NULL&&root->left->right==NULL){
leftNum+=root->left->val;
}
return leftNum+sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
}
};
222.完全二叉树的节点个数
文章链接:https://programmercarl.com/0222.完全二叉树的节点个数.html
题目链接:https://leetcode.cn/problems/count-complete-tree-nodes/
总结:直接做一个遍历即可
class Solution {
public:
int countNodes(TreeNode* root) {
if(root==NULL) return 0;
return 1+countNodes(root->left)+countNodes(root->right);
}
};
标签:return,root,随想录,二叉树,https,NULL,第十五天,left
From: https://www.cnblogs.com/VickyWu/p/18531186