每日一练(27):二叉树的深度

简介: 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。


例如:


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


   3

  / \

 9  20

   /  \

  15   7


返回它的最大深度 3 。


提示:


节点总数 <= 10000


来源:力扣(LeetCode)


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


方法一:递归


后续遍历:


按照递归三部曲,来看看如何来写。


1.确定递归函数的参数和返回值:参数就是传入树的根节点,返回就返回这棵树的深度,所以返回值为int类型。


代码如下:


int getDepth(TreeNode* node)


2.确定终止条件:如果为空节点的话,就返回0,表示高度为0。


代码如下:


if (node == NULL) return 0;


3.确定单层递归的逻辑:先求它的左子树的深度,再求右子树的深度,最后取左右深度最大的数值 再+1 (加1是因为算上当前中间节点)就是目前节点为根节点的树的深度。


int leftDepth = getDepth(node->left);       // 左
int rightDepth = getDepth(node->right);     // 右
int depth = 1 + max(leftDepth, rightDepth); // 中
return depth;
//1简化前
int getDepth(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = getDepth(node->left);       // 左
    int rightDepth = getDepth(node->right);     // 右
    int depth = 1 + max(leftDepth, rightDepth); // 中
    return depth;
}
int maxDepth(TreeNode* root) {
    return getDepth(root);
}
//2简化后
int maxDepth(TreeNode* root) {
    return (root == NULL) ? 0 : 1 + max(maxDepth(root->left), maxDepth(root->right));
}


方法二:迭代法(BFS)


使用迭代法的话,使用层序遍历是最为合适的,因为最大的深度就是二叉树的层数,和层序遍历的方式极其吻合


int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int depth = 0;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
        depth++;
        int size = que.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = que.front();
            que.pop();
            if (node->left) {
                que.push(node->left);
            }
            if (node->right) {
                que.push(node->right);
            }
        }
    }
    return depth;
}
目录
相关文章
|
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年阿里云域名备案流程(新手图文详细流程)
|
7天前
|
前端开发
Promise的then方法返回的新Promise对象的状态为“失败(Rejected)”时,链式调用会如何执行?
Promise的then方法返回的新Promise对象的状态为“失败(Rejected)”时,链式调用会如何执行?
242 127