110. 平衡二叉树
2023-03-14 22:50:36 时间
自上而下递归:
class Solution {
public:
bool isBalanced(TreeNode* root)
{
if(root==NULL)
return true;
//平衡条件:左右子树高度差小于1,并且左右子树都是平衡树
return abs(getHigh(root->left)-getHigh(root->right))<=1&&isBalanced(root->left)&&isBalanced(root->right);
}
//计算二叉树高度的函数
int getHigh(TreeNode* root)
{
return root==NULL?0:max(getHigh(root->left),getHigh(root->right))+1;
}
};
自下而上的递归:
class Solution {
public:
int height(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
//发现一个子树不平衡,那么整棵树就不可能平衡
if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return max(leftHeight, rightHeight) + 1;
}
}
bool isBalanced(TreeNode* root) {
return height(root) >= 0;
}
};
相关文章
- AWS云上混沌工程实践之对照实验设计篇
- 使用Amazon WorkDocs, WorkMail以及WorkSpaces实现统一,安全,灵活的企业内容协作
- 轻松使用 Serverless 架构实现微信公众号后台开发
- 了解 AWS 服务和解决方案 — AWS 5 月在线技术讲座
- SAP on AWS 更新 – 客户案例研究、纵向扩展、横向扩展等
- 中国内容分发服务已经推出! Amazon CloudFront 宣布在中国大陆推出新的 CDN
- Deadline 使用 SPOT Event Plugin 开启低成本渲染农场
- 使用 Amazon CloudWatch Events 构建无服务器管道
- Open Distro for Elasticsearch 0.9.0 现已推出
- 全新 – Amazon S3 批量操作
- 使用 AWS Transit Gateway & Direct Connect 集中和简化网络连接
- 新用途 – Amazon Managed Blockchain – 创建 & 管理可扩展的区块链网络
- AWS DeepRacer League 虚拟赛道现已开放,立即训练您的模型吧!
- 现已推出 – 适用于紧密耦合的 HPC 工作负载的 Elastic Fabric Adapter (EFA)
- Open Distro for Elasticsearch 的 LDAP 集成
- 现在开放 – AWS 亚太地区(香港)区域
- 现已推出 – AMD EPYC 支持的 Amazon EC2 T3a 实例
- 新增功能 – 使用 AWS Systems Manager Parameter Store 查询 AWS 区域、终端节点等
- AWS re:Inforce 2019 – 安全性、身份和合规性
- 利用 Amazon Cognito,安全地验证用户名