LeetCode刷题（35）～二叉树的最大深度【递归+DFS+BFS 注：DFS未懂！】

题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

  

 

  
1
 

返回它的最大深度 3 。

解答

代码（递归）

 int maxDepth(TreeNode* root) { if(root==NULL) return 0; return 1+max(maxDepth(root->left),maxDepth(root->right)); }

  

 

  
1
  
2
  
3
  
4
  
5
 

运行结果

代码（BFS：广度遍历）

 if (root == nullptr) return 0; queue<TreeNode*> Q; Q.push(root); int ans = 0; while (!Q.empty()) { int sz = Q.size(); // 将下一层节点全部压入队列 while (sz > 0) { TreeNode* node = Q.front();Q.pop(); if (node->left) Q.push(node->left); if (node->right) Q.push(node->right); sz -= 1; } ans += 1; } return ans;

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

运行结果

代码（DFS：深度遍历）

int maxDepth(TreeNode* root) { if(root==NULL) return 0; stack<pair<TreeNode*,int>> s; TreeNode* p=root; int Maxdeep=0; int deep=0; while(!s.empty()||p!=NULL)//若栈非空，则说明还有一些节点的右子树尚未探索；若p非空，意味着还有一些节点的左子树尚未探索 { while(p!=NULL)//优先往左边走 { s.push(pair<TreeNode*,int>(p,++deep)); p=p->left; } p=s.top().first;//若左边无路，就预备右拐。右拐之前，记录右拐点的基本信息 deep=s.top().second; if(Maxdeep<deep) Maxdeep=deep;//预备右拐时，比较当前节点深度和之前存储的最大深度 s.pop();//将右拐点出栈；此时栈顶为右拐点的前一个结点。在右拐点的右子树全被遍历完后，会预备在这个节点右拐 p=p->right; } return Maxdeep; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
参考：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/cde-san-chong-fang-fa-shi-xian-you-zhu-jie-by-zzxh/

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/107923364