二叉树深度--剑指offer。三种方法—

二叉树深度--剑指offer。三种方法——BFS、DFS

1、后序遍历（DFS）

树的后序遍历/深度优先搜索往往利用递归和栈。

算法解析：

1、终止条件：当root空，说明越过了叶节点，因此返回深度0

2、递推：实质上是对树做后序遍历

1、计算左子树深度

2、计算右子树深度

3、返回值：返回的树的深度是左子树和右子树二者中最大的。同时要加上根节点这一层。

1 int maxDepth(struct TreeNode* root){
2     if(root==NULL)
3     {
4         return 0;
5     }
6     int left=maxDepth(root->left);
7     int right=maxDepth(root->right);
8     return left>right?left+1:right+1;
9 }

2、BFS

树的层序遍历 / 广度优先搜索往往利用队列实现。
关键点：每遍历一层，则计数器 +1，直到遍历完成，则可得到树的深度。
算法解析：
1、特例处理：当 root 为空，直接返回深度 0 。
2、初始化：队列 queue （加入根节点 root ），计数器 res = 0。
3、循环遍历：当 queue 为空时跳出。

初始化一个空列表 tmp ，用于临时存储下一层节点；
遍历队列：遍历 queue 中的各节点 node ，并将其左子节点和右子节点加入 tmp；
更新队列：执行 queue = tmp ，将下一层节点赋值给 queue；
统计层数：执行 res += 1 ，代表层数加 11；

4、返回值：返回 res 即可

作者：jyd
链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/solution/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 1 typedef struct queue
 2 {
 3     int front;
 4     int rear;
 5     struct TreeNode *data[10000];
 6 }QUEUE;
 7 
 8 int maxDepth(struct TreeNode* root){
 9     int n=0;
10     if(root==NULL)
11     {
12         return 0;
13     }
14     QUEUE q;
15     q.data[0]=root;
16     q.rear=1;q.front=0;
17     while(q.rear!=q.front)
18     {
19         int levelcount=q.rear-q.front;
20         for(int i=0;i<levelcount;i++)
21         {
22              if(q.data[q.front]->left)
23             {
24                 q.data[q.rear++]=q.data[q.front]->left;
25             }
26             if(q.data[q.front]->right)
27             {
28                 q.data[q.rear++]=q.data[q.front]->right;
29             } 
30             q.front++;
31         }
32         n++;
33     }
34     return n;
35 }