【二叉树】LC 104.二叉树的最大深度

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析DFS递归解法时间复杂度O(n) 、空间复杂度O(h)BFS层序遍历解法时间复杂度O(n)、空间复杂度O(w)2、解题代码递归解法时间复杂度O(n) 、空间复杂度O(h)迭代解法时间复杂度O(n)、空间复杂度O(w)三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接104.二叉树的最大深度2、题目描述二、个人思路整理1、思路分析DFS递归解法时间复杂度O(n) 、空间复杂度O(h)递归终止条件当前节点为空则直接返回递归体分别递归计算左、右子树的深度取最大值当前节点所在子树的深度即为最大值1。复杂度分析时间复杂度O ( n ) \mathcal{O}(n)O(n)每个节点都会被遍历一次其中n nn为节点总数。空间复杂度O ( h ) \mathcal{O}(h)O(h)取决于递归调用的栈深度其中h hh为树的高度最坏情况下退化为链表时为O ( n ) \mathcal{O}(n)O(n)平衡二叉树时为O ( log ⁡ n ) \mathcal{O}(\log n)O(logn)。BFS层序遍历解法时间复杂度O(n)、空间复杂度O(w)利用队列依次【循环将每层的节点入队在处理每层节点时循环出队元素在每个节点出队时将其左、右孩子入队如果有方便下一轮循环】同时在处理完每层节点时记录层层数直至队列为空最终答案即为最大深度。复杂度分析时间复杂度O ( n ) \mathcal{O}(n)O(n)遍历所有节点。空间复杂度O ( w ) \mathcal{O}(w)O(w)队列中最多保存树中节点较多那一层的节点数即树的最大宽度w ww。2、解题代码递归解法时间复杂度O(n) 、空间复杂度O(h)/** * 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) {} * }; */classSolution{public:intmaxDepth(TreeNode*root){if(rootnullptr){return0;}returnmax(maxDepth(root-left),maxDepth(root-right))1;}};迭代解法时间复杂度O(n)、空间复杂度O(w)/** * 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) {} * }; */classSolution{public:intmaxDepth(TreeNode*root){if(rootnullptr){return0;}queueTreeNode*q;q.push(root);intans0;while(!q.empty()){intsizeq.size();//记录当前层的节点数控制下面循环次数如果不记录这个值而是直接用q.size()作为循环判断条件则会导致死循环//处理当前层的size个节点同时将下一层即这个size个节点的孩子放入队列while(size--){TreeNode*tmpq.front();q.pop();if(tmp-left!nullptr){q.push(tmp-left);}if(tmp-right!nullptr){q.push(tmp-right);}}ans;//每处理完一层深度1}returnans;}};三、知识风暴DFS与BFS易错点总结BFS 必须先固定每层节点数进入每层遍历前必须用int size q.size();固定当前层节点数量切忌直接把q.size()写在循环条件中因为入队新节点会改变q.size()导致把下一层节点混入当前层引发死循环或深度统计错误。深度累加时机ans必须在处理完一整层节点后执行而非每弹出单个节点就累加。