算法数据结构——数的深搜和广搜（dfs和bfs）
2024-08-27 19:42:52
leetcode104 二叉树的最大深度 https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
深度搜索分两种：递归（使用栈）
广度搜索：非递归（使用队列）
1. 广度搜索bfs：（标准模板）（也可建议用c++的queue，deque是双端队列，可以实现头尾的插入和弹出）
1 /**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 int maxDepth(TreeNode* root) {
13 deque<TreeNode*> d;
14 if(!root)
15 return 0;
16 d.push_back(root);
17 int num = 0;
18 while(!d.empty())
19 {
20 int t = d.size();
21 //cout<<"t:"<<t<<endl;
22 for(int i=0;i<t;i++)
23 {
24 TreeNode *p = d.front();
25 d.pop_front();
26 if(p->left)
27 d.push_back(p->left);
28 if(p->right)
29 d.push_back(p->right);
30 }
31 num++;
32 }
33 return num;
34 }
35 };
2. 深搜，递归
1 /**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 int maxDepth(TreeNode* root) {
13 if(!root)
14 return 0;
15
16 return max(maxDepth(root->left), maxDepth(root->right)) +1;
17 }
18 };
最新文章
- MySQL的基本知识 -- 命令
- VS2012 error C2664: “std::make_pair”:无法将左值绑定到右值引用
- Validform —— 再也不用担心“表单验证”！
- 【Git】安装以及第一次使用Git和GitHub傻瓜教程
- MyBatis魔法堂：ResultMap详解
- JavaScript中两个感叹号（!!）的作用是什么？
- HDOJ 1062 Text Reverse
- 130道ASP.NET面试题
- 实例源码--Android底部功能分类Tab使用实例
- Mac - 更新 Ruby
- Svn忽略配置
- SQL Server不区分大小写的问题
- appcan里面模板的使用
- java变量和数据类型总结
- conky 1.10以后的新配置格式
- .NET MD5 加密
- webpack4与babel配合使es6代码可运行于低版本浏览器
- MySQL数据库详解之"双1设置"的数据安全的关键参数案例分享
- SVG绘制太极图
- Android 二维码扫描/生成