品牌网站建设的作用,西安建站费用,青岛网站建设方案书,最新招总代理项目文章目录 写在前面Tag题目来源解题思路方法一#xff1a;递归方法二#xff1a;迭代 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于本题涉及到的… 文章目录 写在前面Tag题目来源解题思路方法一递归方法二迭代 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【递归】【迭代】【二叉树】 题目来源
104. 二叉树的最大深度 解题思路
通常二叉树的问题都有两种解法递归和迭代。
方法一递归
思路
递归是一种模拟栈空间后进先出的特点隐式枚举节点来完成计算任务。递归写法的要点是递归出口的寻找以及向下 “递” 和本层的联系。递归的 “递” 一直 “递” 到递归出口“归” 则是自底向上的将底层信息往上传。
递归的出口为节点为空直接返回 0。
本题的向下 “递” 和本层的联系为深度增加了 1。 写递归实现的一个重要思想是自己实现的递归就是正确的哪怕递归实现还没开始写都可以先调用 算法
从根节点开始递归计算深度递归函数为
递归出口为当前节点为空即 node nullptr递归计算左子树的最大深度递归计算右子树的最大深度最后返回左右子树的最大深度并加上 1。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {return root? 1 max(maxDepth(root-left), maxDepth(root-right)) : 0;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为二叉树的节点个数。
空间复杂度 O ( n ) O(n) O(n)最坏情况下二叉树退化成一条链此时递归需要的栈空间为 O ( n ) O(n) O(n)。
方法二迭代
思想
相对于递归迭代则是显示的枚举节点完成计算任务。
计算最大深度直白的想法是 “数” 这棵二叉树有多少层。如何 “数”用层序遍历本质就是迭代。
算法
维护一个队列 q 用来存放节点int 整型变量 depth 记录深度
首先将根节点存入队列依次枚举队列中的节点 node 如果有左子节点或者右子节点则加入队列即记录新的一层节点将当前枚举的节点弹出队列。 枚举完一层节点之后深度 depth 1最后返回 depth。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {if (!root)return 0;queueTreeNode* q;q.push(root);int depth 0;while (!q.empty()) {int n q.size(), i 0;while (i n) {TreeNode* curr q.front();q.pop();if (curr-left ! nullptr)q.push(curr-left);if (curr-right ! nullptr)q.push(curr-right);}depth;}return depth;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为二叉树的节点个数。
空间复杂度此方法空间的消耗取决于队列存储的元素数量其在最坏情况下会达到 $O(n)#。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
