二叉树的最大深度（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
2
3
4
5
6
7
8
9

代码效率

广度搜索（层序查找）

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

层序查找的思路

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

C++代码

这个代码排版有点丑Sorry！

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> 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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码效率

总结

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