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

题目

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

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

示例

示例 1：

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

示例 2：

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

分析

深度优先搜索(递归)

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

时间复杂度：O()，  为二叉树节点的个数

空间复杂度：O()，  表示二叉树的高度

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()，  为二叉树节点的个数

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

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 和 30return 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;
}