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