做外贸开通哪个网站好,wordpress 消息通知,合肥做网站的网络公司,南京app开发定制题目
给定一个二叉树 root #xff0c;返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;3示例 2#xff1a; 输入#xff1a;root [1,n…题目
给定一个二叉树 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;}queueTreeNode* 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::queueint myQueue;
入队(push)
push 方法用于将一个元素添加到队列的尾部。
#include iostream
#include queue
int main() {std::queueint myQueue;// 入队操作myQueue.push(10);myQueue.push(20);myQueue.push(30);return 0;
}
出队(pop)
pop 方法用于移除队列头部的元素但不返回该元素的值。
#include iostream
#include queue
int main() {std::queueint myQueue;myQueue.push(10);myQueue.push(20);myQueue.push(30);// 出队操作myQueue.pop();// 此时队列中剩下 20 和 30return 0;
}
访问头元素(front)
front 方法用于返回队列头部的元素但不将其从队列中移除。
#include iostream
#include queue
int main() {std::queueint 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::queueint 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;
}
