每日一练(28):平衡二叉树

简介: 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。


示例 1:


给定二叉树 [3,9,20,null,null,15,7]


3

/ \

9  20

/  \

15   7


返回 true 。


示例 2:


给定二叉树 [1,2,2,3,3,null,null,4,4]


1

 / \

2   2

/ \

3   3

/ \

4   4


返回 false 。


限制:


0 <= 树的结点个数 <= 10000


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/probl...


方法一:后序遍历(DFS)


dfs计算思路:


  • 对于空结点,深度为0
  • 当前深度是左右子树深度的最大值+1, 有效情况直接返回深度
  • 一旦发现左右子树的深度差异超过1,则认为无效,返回-1
  • 一旦发现返回是-1, 直接返回-1


bool isBalanced(TreeNode* root) {
    return (dfs(root) != -1);
}
int dfs(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    int left = dfs(node->left);
    if (left == -1) {
        return -1;
    }
    int right = dfs(node->right);
    if (right == -1) {
        return -1;
    }
    return abs(left - right) > 1 ? -1 : max(left, right) + 1;//当前深度是左右子树深度的最大值+1, 有效情况直接返回深度
}


方法二:前序遍历


对于当前遍历到的节点,首先计算左右子树的高度,如果左右子树的高度差是否不超过 11,再分别递归地遍历左右子节点,并判断左子树和右子树是否平衡。这

是一个自顶向下的递归的过程


int height(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return max(height(root->left), height(root->right)) + 1;
}
bool isBalanced(TreeNode* root) {
    if (root == nullptr) {
        return true;
    }
    return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}


目录
相关文章
|
12月前
|
安全 搜索推荐 Android开发
安卓与iOS:两大操作系统的比较
本文将深入探讨安卓和iOS两大操作系统的差异,包括它们的设计理念、用户界面、应用生态以及安全性等方面。通过对比分析,我们可以更好地理解这两个系统各自的优势和不足,从而为用户在选择手机时提供一些参考。
|
3天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
14天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1304 5
|
13天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1332 87
|
2天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
184 82
2025年阿里云域名备案流程(新手图文详细流程)