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

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

104.二叉树的最大深度

2、题目描述

二、个人思路整理

1、思路分析

DFS递归解法（时间复杂度O(n) 、空间复杂度O(h)）

1. 递归终止条件：当前节点为空，则直接返回；
2. 递归体：
   分别递归计算左、右子树的深度，取最大值；当前节点所在子树的深度即为最大值+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(root==nullptr){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(root==nullptr){return0;}queue<TreeNode*>q;q.push(root);intans=0;while(!q.empty()){intsize=q.size();//记录当前层的节点数，控制下面循环次数，如果不记录这个值，而是直接用q.size()作为循环判断条件，则会导致死循环//处理当前层的size个节点，同时将下一层（即这个size个节点的孩子）放入队列while(size--){TreeNode*tmp=q.front();q.pop();if(tmp->left!=nullptr){q.push(tmp->left);}if(tmp->right!=nullptr){q.push(tmp->right);}}ans++;//每处理完一层，深度+1}returnans;}};

三、知识风暴

• DFS与BFS

易错点总结

1. BFS 必须先固定每层节点数：
   进入每层遍历前必须用int size = q.size();固定当前层节点数量；切忌直接把q.size()写在循环条件中，因为入队新节点会改变q.size()，导致把下一层节点混入当前层，引发死循环或深度统计错误。
2. 深度累加时机：ans++必须在处理完一整层节点后执行，而非每弹出单个节点就累加。