阅读量:0
解题思路：
\qquad 最大深度可以想到使用DFS(深度优先)或BFS(广度优先)来解决。
\qquad DFS：一般用 递归 or 迭代+栈。递归实现较为简单。
\qquad BFS：一般用 迭代+队列。
DFS：
\qquad 对于每个节点，将左子树的最大深度与右子树的最大深度比较，选取较大值+1，即为当前节点树的最大深度。空节点的最大深度为0.
int maxDepth(TreeNode* root) { if(!root) { return 0; } return max(maxDepth(root->left), maxDepth(root->right)) + 1; } BFS：
\qquad 从根节点开始，每次将同深度的节点加入队列，再遍历队列节点，将其左右子节点加入队列。来计算深度。
\qquad 再次回顾C++STL 队列数据结构queue的用法。
| Queue | First In First Out（FIFO） | 复杂度 |
|---|---|---|
| push() | 队尾添加一个元素 | O(1) |
| pop() | 队首移除一个元素（若空队列会报错） | O(1) |
| front() | 查看队首元素 | O(1) |
| back() | 查看队尾元素 | O(1) |
| size() | 队列元素数量 | O(1) |
| empty() | 队列是否为空（空队列为 True） | O(1) |
int maxDepth(TreeNode* root) { if(!root) return 0; int num = 0, cnt = 0; queue<TreeNode*> q; q.push(root); while(!q.empty()) { num = q.size(); cnt++; while(num > 0) { TreeNode* node = q.front(); q.pop(); if(node->left) q.push(node->left); if(node->right) q.push(node->right); num--; } } return cnt; } STL时间复杂度总结 https://blog.csdn.net/2302_79440616/article/details/139326935
