原题链接–>戳这里直达

二叉树的最大深度

• 深度搜索（递归）
• • 递归思想和详解
  • C++代码
  • 代码效率
• 广度搜索（层序查找）
• • 层序查找的思路
  • C++代码
  • 代码效率
• 总结

深度搜索（递归）

最近新学习了树形结构，上课的时候听到老师说的深度搜索，感觉很神奇，其实思想和递归有异曲同工之处。

递归思想和详解

写递归要有思路
其实递归就像之前写的数学题，先把一个东西分成几部分，然后将它们分别当做一个整体，再重复操作。（可能更抽象了，sorry）
鄙人语言匮乏，献上一个图，哪里不对可以指出，我太菜了嘤嘤嘤

1.确定递归函数的参数和返回值
在这个题中参数就是左右指针，参数类型为指针类型，返回的值为整型层数
2.确定终止条件
当指针到最后便会指向NULL，此时递归终止，该向上弹出
3.确定单层递归的逻辑
其实这个题里面递归的每层没什么要处理的信息，就是计数，看什么时候指针指到NULL，然后向上弹出，比较左右两边谁弹出的层数多，就记录谁，然后再与更大方向上的左右指针层数比较。

C++代码

class Solution {
public:int maxDepth(TreeNode* root) {if(!root)return 0;int deep=max(maxDepth(root->left),maxDepth(root->right))+1;return deep;}};

代码效率

广度搜索（层序查找）

这个思路相对简单，就是树里面老师说的，层序查找，一层一层查找

层序查找的思路

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式需要借用一个辅助数据结构即队列来实现。
1->先将根节点放入队列，然后层数加一，队列长度(size)记为1，将根节点弹出队列
2-> 将根节点的左（root->left）右指针(root->right)再放入，队列长度记为2，依次弹出左节点，再将左节点的左右指针放入队列，重复弹出右节点，再将右节点的左右指针放入队列，在重新计算队列的长度，
3->重复操作，直到没有左右不能再分出节点即队列（que.empty=0）长度为0为止。
4->输出size为0的次数也就是层数。
队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

C++代码

这个代码排版有点丑Sorry！

class Solution {
public:int maxDepth(TreeNode* root) {queue que;if(root!=NULL) que.push(root);int layer=0;while(!que.empty()){int size=que.size();while(size){TreeNode* node=que.front();que.pop();if(node->left) que.push(node->left);if(node->right) que.push(node->right);size--;}layer++;}return layer;}

代码效率

总结

两种搜索方法于图于数都可用，但是从代码效率来看，递归要快，但是第二个理解更容易。