当前位置: 首页 > article >正文

LeetCode hot 100—二叉树的最大深度

题目

给定一个二叉树 root ,返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:3

示例 2:

输入:root = [1,null,2]
输出:2

分析

深度优先搜索(递归)

核心思想:对于一个二叉树,它的最大深度等于其左子树和右子树的最大深度中的较大值加 1(加上当前根节点)。如果根节点为空,那么深度为 0。

时间复杂度:O(n), n 为二叉树节点的个数

空间复杂度:O(h), h 表示二叉树的高度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        return max(leftDepth, rightDepth) + 1;
    }
};

广度优先搜索(迭代)

核心思想:通过队列来存储每一层的节点,每遍历完一层,深度加 1。

时间复杂度:O(n), n 为二叉树节点的个数

空间复杂度:O(m),m 是二叉树中节点数最多的那一层的节点数

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        queue<TreeNode*> nodeQueue;
        nodeQueue.push(root);
        int depth = 0;
        while (!nodeQueue.empty()) {
            int levelSize = nodeQueue.size();
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* current = nodeQueue.front();
                nodeQueue.pop();
                if (current->left) {
                    nodeQueue.push(current->left);
                }
                if (current->right) {
                    nodeQueue.push(current->right);
                }
            }
            ++depth;
        }
        return depth;
    }
};

知识充电

queue 队列

queue(队列)是一种重要的数据结构,遵循先进先出(FIFO, First-In-First-Out)的原则。

基本操作

初始化
#include <queue>
// 定义一个存储 int 类型元素的队列
std::queue<int> myQueue;
入队(push)

push 方法用于将一个元素添加到队列的尾部。

#include <iostream>
#include <queue>
int main() {
    std::queue<int> myQueue;
    // 入队操作
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);
    return 0;
}
出队(pop)

pop 方法用于移除队列头部的元素,但不返回该元素的值。

#include <iostream>
#include <queue>
int main() {
    std::queue<int> myQueue;
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);
    // 出队操作
    myQueue.pop();
    // 此时队列中剩下 20 和 30
    return 0;
}
访问头元素(front)

front 方法用于返回队列头部的元素,但不将其从队列中移除。

#include <iostream>
#include <queue>
int main() {
    std::queue<int> myQueue;
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);
    // 访问队列头部元素
    int frontElement = myQueue.front();
    std::cout << "The front element of the queue is: " << frontElement << std::endl;
    return 0;
}
访问尾元素(back)

back 方法用于返回队列尾部的元素,但不将其从队列中移除。

#include <iostream>
#include <queue>
int main() {
    std::queue<int> myQueue;
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);
    // 访问队列尾部元素
    int backElement = myQueue.back();
    std::cout << "The back element of the queue is: " << backElement << std::endl;
    return 0;
}

http://www.kler.cn/a/576451.html

相关文章:

  • ubuntu22.04安装P104-100一些经验(非教程)
  • Spring Boot集成Minio笔记
  • pytest结合allure
  • 音频3A测试--AGC(自动增益)和NS(降噪)测试
  • 数组扩展【ES6】
  • 青少年编程与数学 02-010 C++程序设计基础 30课题、操作符重载
  • Cursor + IDEA 双开极速交互
  • 1658. 将 x 减到 0 的最小操作数
  • 代码随想录第五十天| 图论理论基础
  • Java集合框架之Collections工具类
  • 人工智能之数学基础:线性代数中的行列式的介绍
  • Node.js 报错 ENOBUFS 处理方案
  • Manus AI:从爆火到争议,AI Agent的未来之路
  • 服务器分区调整方案(不影响服务)
  • 网络安全规划重安全性需求
  • MySQL 连接报错: “Public Key Retrieval is not allowed“ 问题解决方案
  • Ubuntu 下 nginx-1.24.0 源码分析 - ngx_init_cycle 函数
  • PPT 小黑第21套
  • 【AI赋能】AI 工具生成视频教材:从创意到成品的全流程指南
  • 扩展------项目中集成阿里云短信服务