更多干货就在我的个人博客 BlackBlog.tech 欢迎关注！
也可以关注我的csdn博客：黑哥的博客
谢谢大家！
很久没有进行练习了，手都生疏了不少。前一段时间完成30道DFS题目的练习，现在开始BFS，预计做完BFS分类中的所有中等难度题。
LeetCode中的分类并不是非常的标准，BFS的题目中很多用DFS也可以解答，只要能够解出，不一定绝对要使用LeetCode建议的算法。
给个目录：
LeetCode102 二叉树的层次遍历
LeetCode103 二叉树的锯齿形层次遍历
LeetCode127 单词接龙
LeetCode787 K 站中转内最便宜的航班
LeetCode752 打开转盘锁
LeetCode200 岛屿的个数
LeetCode199 二叉树的右视图
LeetCode210 课程表 II
LeetCode279 完全平方数
LeetCode310 最小高度树
LeetCode863 二叉树中所有距离为 K 的结点
LeetCode133 克隆图
LeetCode102 二叉树的层次遍历
题目
给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
C++代码
class Solution {
public:
map<int,vector<int>> hash; //新建一个map用于存储结果
vector<vector<int>> levelOrder(TreeNode* root) {
dfs(root,0);//dfs开始
vector<vector<int>> res; //res存储最终结果
for(auto key:hash){
res.push_back(key.second); //将map转换为vector
}
return res;//返回结果
}
void dfs(TreeNode* root, int depth){
if(!root) return;//如果是空节点 直接返回
hash[depth].push_back(root->val); //同一层次的节点放入一个vector中
dfs(root->left,depth+1);//遍历左子树
dfs(root->right,depth+1);//遍历右子树
}
};
体会
DFS+记录深度，非常经典的树的遍历题目，熟悉DFS应该在三分钟内可以A掉，具体内容请看注释。
LeetCode103 二叉树的锯齿形层次遍历
题目
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
C++代码
class Solution {
public:
map<int,vector<int>> hash;
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
dfs(root,0);
vector<vector<int>> res;
for(auto key:hash){
if(key.first%2){ //偶数层反转数组
reverse(key.second.begin(),key.second.end());
res.push_back(key.second);
}
else res.push_back(key.second); //奇数层正常放入
}
return res;
}
void dfs(TreeNode* root, int depth){
if(!root) return;//如果当前节点为空 返回
hash[depth].push_back(root->val); //同一层节点放在一个vector中
dfs(root->left,depth+1); //遍历左子树
dfs(root->right,depth+1); //遍历右子树
}
};
体会
本题与上一题思路完全一致，唯一的区别在于偶数层节点需要反向输出达到最后的效果，奇数层节点正常输出。
LeetCode127 单词接龙
题目
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中，所以无法进行转换。
C++代码
class Solution {
public:
int min_length = INT_MAX; //记录最短路径
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
queue<pair<string,int>> que;//建立一个队列 记录当前字符串与路径长度
que.push({beginWord,1});//放入起始字符串 路径长度为1
vector<int> visited(wordList.size(),0); //用来记录wordList的访问情况
while(!que.empty()){
auto tmp = que.front(); //取出队首元素
que.pop(); //出队
if(tmp.first==endWord && tmp.second<min_length){ //如果队首元素与最终字符串相同 且 路径长度小于min_length 则修改min_length
min_length = tmp.second;
}
//寻找当前队首字符串的下一个变换字符串
for(int i=0;i<wordList.size();i++){
if(visited[i]) continue; //如果当前字符串被访问过 则跳过
else if (cmp(tmp.first,wordList[i])!=1) continue; //如果当前字符串与队首字符串变换字符数量不为1 则跳过
else { //否则新的字符串入队 并修改当前长度
que.push({wordList[i],tmp.second+1});
visited[i] = 1;
}
}
}
if(min_length==INT_MAX) return 0; //如果当前长度为INT_MAX证明没有找到 返回0
else return min_length; //否则返回当前最小长度
}
//判断src与dst两个字符串不相同字符的个数
int cmp(string src,string dst){
int count = 0;
for(int i=0;i<src.length();i++){
if(src[i]!=dst[i]) count ++;
}
return count;
}
};
体会
这个题目与POJ上的一道题目非常类似，本题采用BFS算法。首先创建一个队列，队列中需要包括当前的字符串与路径长度，向队列中存入beginWord，之后重复如下过程：遍历wordList寻找与队首字符串仅一个字母不同的字符串，寻找到之后存入队列中，直到寻找到endWord，比较当前的长度与min_length，选小的作为min_length。最后返回min_length。
LeetCode787 K 站中转内最便宜的航班
题目
有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。
示例 1:
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
示例 2:
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
C++代码
class Solution {
public:
int min_value = INT_MAX;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
queue<vector<int>> que; //建立一个队列 队列存储的是 价值和 与 路径。 数组的第一个元素为当前路径的价值和，后面的元素为当前的路径。
que.push({0,src}); //起点入队
while(!que.empty()){ //如果队列不为空
auto tmp = que.front(); //取出队首元素
que.pop();
if(tmp[tmp.size()-1]==dst){ //如果当前路径已经碰到终点
if(tmp.size()-1<=K+2 && tmp[0]<min_value) min_value = tmp[0]; //且当前路径的长度小于K+2（中转点+起点+终点）且当前路径的价值小于min_value 更新 min_value。
}
if(tmp.size()>K+2 || tmp[0]>min_value) continue;//剪枝 如果当前路径的长度>K+2或者当前路径的价值大于min_value都不在进行搜索
for(auto key:flights){ //遍历flights
if(tmp[tmp.size()-1]==key[0] && find(tmp.begin()+1,tmp.end(),key[1])==tmp.end()){ //find函数用来保证当前路径中没有重复节点
vector<int> new_vec; //创建一个新的临时vec
new_vec.insert(new_vec.end(),tmp.begin(),tmp.end()); //将tmp的内容全部放入new_vec
new_vec[0]+= key[2]; //new_vec的价值 = tmp的价值 + 新节点的价值
new_vec.push_back(key[1]); //将新的节点放入new_vec中
que.push(new_vec);//将new_vec放入que
}
}
}
if(min_value==INT_MAX) return -1; //如果min_value等于INT_MAX证明没有找到 返回-1
else return min_value; //否则返回最小长度
}
};
体会
经典BFS算法，这个题需要考虑一个问题。题目中虽然说了没有环路，但是两个节点间有往返的情况。对于这种情况我们在BFS的过程中需要存储整个路径，用来判断是否会出现重复节点。由于K有的时候会非常大，搜索的深度会非常深，这时候要注意剪枝。如果当前路径的长度>K+2或者当前路径的价值大于min_value都不在进行搜索，这样剪枝可以让效率成倍的提升。
LeetCode752 打开转盘锁
题目
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1
C++代码
class Solution {
public:
int openLock(vector<string>& deadends, string target) {
string beginStr = "0000"; //初始字符
set<string> dead(deadends.begin(),deadends.end()); //将deadends转化为set 用来提高检索速度
set<string> visited; //用来记录已经访问过的号码
char flag_1 = '9'+1; //用来处理9->0
char flag_2 = '0'-1; //用来处理0->9
int min_length = INT_MAX;//用来记录最短路径的长度
visited.insert(beginStr); //将初始字符设置为访问
queue<pair<int,string>> que; //建立一个队列 队列中记录当前节点与深度
que.push({0,beginStr});//放入其实节点
if(dead.count("0000")) return -1; //如果dead中有0000 直接返回-1
while(!que.empty()){
auto tmp = que.front(); //取出队列中第一个元素
que.pop();
if(tmp.second == target && tmp.first<min_length){ //如果当前节点就是target 且深度小于当前的min_length，更新min_length。
min_length = tmp.first;
}
if(tmp.first>min_length) continue; //剪枝 如果当前深度大于min_length则不需要再搜索
for(int i=0;i<4;i++){ //对于密码中的每一位做+1 -1 操作
string str_plus = tmp.second;
string str_subs = tmp.second;
str_plus[i]+=1;
str_subs[i]-=1;
if(str_plus[i]==flag_1){ //9->0
str_plus[i] = '0';
}
if(str_subs[i]==flag_2){ //0->9
str_subs[i] = '9';
}
if(!dead.count(str_plus) && !visited.count(str_plus)) { //如果dead与visited中都不存在 str_plus，则将其放入队列。
que.push({tmp.first+1,str_plus});
visited.insert(str_plus);
}
if(!dead.count(str_subs) && !visited.count(str_subs)) { //如果dead与visited中都不存在 str_subs，则将其放入队列。
que.push({tmp.first+1,str_subs});
visited.insert(str_subs);
}
}
}
return min_length == INT_MAX? -1: min_length; //返回最终结果
}
};
体会
经典BFS+剪枝。将问题转化为一个图，每一个节点都与其他8个节点相连接，0000与0001、0009、0010、0090、0100、0900、1000、9000这个八个节点相连，以此类推。使用BFS逐层遍历这个图，找到答案并记录下最小路径。这个题直接BFS肯定会爆时间，因为每一个数字都会产生8种变化，不做剪枝数据量将非常大。使用visited数组记录访问过的数据，防止重复。使用set代替vector，set查询复杂度为O(1)，vector查询复杂度为O(n)，要快不少。
LeetCode200 岛屿的个数
题目
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
C++代码
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
if(grid[i][j]=='1') { //如果找到1 将这个点作为种子进行涂色
dfs(grid,i,j);
count++;
}
}
}
return count;
}
void dfs(vector<vector<char>>& grid,int x,int y){
if(x<0||x>grid.size()-1||y<0||y>grid[0].size()-1||grid[x][y]=='0'||grid[x][y]=='2') return; //越界或者碰到0或2 都直接返回
grid[x][y] = '2'; //将当前节点染色
dfs(grid,x+1,y); //对周围四个点做相同操作
dfs(grid,x-1,y);
dfs(grid,x,y+1);
dfs(grid,x,y-1);
}
};
体会
DFS水题。可以把这个题转化为一个涂色问题，找到一个1就将这个区域全涂成2，遍历整个数组，看一功能涂多少个区域。
LeetCode199 二叉树的右视图
题目
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
C++代码
class Solution {
public:
map<int,int> hash; //key是层 value是最右侧的数
vector<int> rightSideView(TreeNode* root) {
vector<int> res;//用于记录最后的结果
dfs(root,0); //从root开始dfs
for(auto key:hash){
res.push_back(key.second);//将hash中的结果按层
}
return res;
}
void dfs(TreeNode* root,int depth){
if(!root) return;
hash[depth] = root->val; //因为是采用先序遍历，所以每次都更新hash 最后的结果就是最右侧的数据
dfs(root->left,depth+1);//dfs左子树
dfs(root->right,depth+1);//dfs右子树
}
};
体会
直接按先序遍历DFS，记录一下每一层的节点就好，水题。
LeetCode210 课程表 II
题目
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。
C++代码
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> in(numCourses,0); //记录入度
map<int,vector<int>> linkGraph; //图的临接表
vector<int> res; //最终结果
queue<int> que; //BFS所用队列
//构建图的邻接表 计算每个节点的入度
for(auto key:prerequisites){
linkGraph[key.second].push_back(key.first);
in[key.first]++;
}
//将所有的起点都放入que中，因为数据中存在图不联通的情况
for(int i=0;i<in.size();i++){
if(in[i]==0) que.push(i);
}
//BFS
while(!que.empty()){
auto tmp = que.front();
if(find(res.begin(),res.end(),tmp)==res.end() && in[tmp]==0)res.push_back(tmp); //如果当前节点没有被添加且入度为0 证明这门课的先修课都完成了，可以将该课添加进res
que.pop();
//遍历邻接表 寻找该节点的邻居
for(auto key:linkGraph[tmp]){
//！！！！！注意顺序
in[key]--; //该节点所有的邻居的入度--
if(in[key]==0) //如果邻居的入度为0 则该邻居可以作为起点放入que中
que.push(key);
}
}
//如果所有节点的入度都为0 证明这个图拓扑可排 输出res 否则输出[]
if(*max_element(in.begin(),in.end())==0) return res;
else return {};
}
};
体会
本题与课程表无太大区别，都是考察图的拓扑排序。本题只是记录课程路径即可，将que中的数据逐个放入res中，即是答案。
几个注意点：
1、图的拓扑排序采用BFS则记录入度，采用DFS则记录出度。
2、图可能不联通，所以要将所有的起点都放入que中
3、去除一点时，先将其邻居点的入度-1，再判断邻居入度是否为0，就是我打了一堆！那里。（卡了我好久T_T）
4、res中可能会有重复，记得去重。
课程表解答请点击
LeetCode279 完全平方数
题目
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
C++代码
class Solution {
public:
int numSquares(int n) {
//DP[i]表示 i可以表示为DP[i]个平方数的和
vector<int> dp(n+1,INT_MAX); //初始化一个DP数组 全部初始化为INT_MAX
for(int i=1;i*i<=n;i++)
dp[i*i] = 1; //将所有的平方数都置为1
for(int i=1;i<n;i++){ //i为普通数
for(int j=1;i+j*j<=n;j++){ //j为平方数的根
dp[i+j*j] = min(dp[i]+1,dp[i+j*j]); //状态转移方程
}
}
return dp[n]; //最终结果
}
};
体会
首先使用DFS进行了尝试，但是爆时间了。
DP的思路：一个非平方数可以看成是一个平方数+一个非平方数。DP[i]表示i可以表示为DP[i]个平方数的和，则非平方数都可以看作是i+jj，i表示一个普通数，j表示一个平方数的根。状态转移方程为dp[i+jj] = min(dp[i]+1,dp[i+jj]),求出能够组成i的最小个数。所有的平方数都只需要自己就可以组成自己，所以是1，其他初始化为无穷。
例子：
n=12
dp[2] = dp[1+11] = min(dp[1]+1，dp[2]) = 2
dp[8] = dp[4+22] = min(dp[4]+1,dp[8]) = 2
dp[12] = dp[8+22] = min(dp[8]+1,dp[12]) = 3
本题参考博客请点击
本题也可以使用四平方定理求解，但个人觉得技巧性太强。
LeetCode310 最小高度树
对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
格式
该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。
你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。
示例 1:
输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
输出: [1]
示例 2:
输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
输出: [3, 4]
说明:
根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。
C++代码
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if(n==1) return{0}; //如果n=1 直接返回[0]
map<int,vector<int>> hash; //hash用于存储图
vector<int> degree(n,0); //degree存储每一个节点的度
for(auto key:edges){ //将edges的内容存储在hash中
hash[key.first].push_back(key.second);
hash[key.second].push_back(key.first);
}
for(auto key:hash){ //计算每个节点的度
degree[key.first] = key.second.size();
}
while (hash.size()>2){ //如果剩余节点个数大于2
vector<int> leaves; //leaves表示叶节点，即 度数为1 的节点
for(int i=0;i<degree.size();i++){
if(degree[i]==1) leaves.push_back(i); //将所有度数为1的节点存入leaves
}
for(auto leaf:leaves){ //删除leaf，并将leaf的邻居节点的度数-1
degree[leaf]=0;
for(auto key:hash[leaf])
degree[key]--;
hash.erase(leaf);
}
}
vector<int> res; //将hash中剩下的1个或2个节点转存到vector中
for(auto key:hash)
res.push_back(key.first);
return res;
}
};
体会
蛮有技巧的一个题目。
首先拿到这个题目，第一个想法就是BFS，将每个节点都做为树的根节点，最后找到树高度最小的根节点，思路很清晰。但是无奈超时了，最后5个数据怎么优化都过不去，无奈换了思路。
本题思路：一个图肯定存在一个最小高度树，所有度为1的节点必为叶节点。我们从叶节点向内搜索，每次都将叶节点删去，并将其邻居节点的度数-1，直到最后仅有一个或两个节点即可，这一个或两个节点就是最小高度树的根节点。
若一个图的最大路径为奇数个节点，则最小高度树的根节点只有1个。
若一个图的最大路径为偶数个节点，则最小高度树的根节点只有2个。
算法流程：
1.以某种方式储存图，同时记录每个节点的度
2.删除度为1的节点，并把与之相连的节点度数减1
3.重复步骤2直到剩下1或2个节点
BFS代码 求大佬优化
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
map<int,vector<int>> hash;
for(auto key:edges){ //存储图
hash[key.first].push_back(key.second);
hash[key.second].push_back(key.first);
}
map<int,vector<int>> res; //key表示深度 value表示能达到当前深度的根节点
int min_length = INT_MAX;
for(auto key:hash){
queue<pair<int,int>> que; //初始化一个队列
vector<int> visited(n,0); //初始化visited防止循环访问
que.push({key.first,0}); //放入第一个节点
visited[key.first]=1; //将第一个节点设置为被访问
while(!que.empty()){
auto tmp = que.front(); //取出队列中的第一个节点
que.pop();
visited[tmp.first]=1; //当前节点设置为访问
if(tmp.second>min_length) break; //如果当前的长度已经大于最小长度 直接弹出
if(find(visited.begin(),visited.end(),0)==visited.end()&&tmp.second<=min_length){ //如果所有的节点都被访问 切当长度小于min_length 修改min_length
min_length = tmp.second;
res[tmp.second].push_back(key.first);
}
for(auto neighbor:hash[tmp.first]){ //将当前节点的neighbor依次入队
if(!visited[neighbor]) {
que.push({neighbor,tmp.second+1});
}
}
}
}
return res[min_length];
}
LeetCode863 二叉树中所有距离为 K 的结点
题目
给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1
提示：
给定的树是非空的，且最多有 K 个结点。
树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
目标结点 target 是树上的结点。
0 <= K <= 1000.
C++代码
class Solution {
public:
map<int,vector<int>> graph;
int graph_size=0;
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
dfs(root);
//BFS寻找第K近的节点
queue<pair<int,int>> que; //BFS所用队列
vector<int> res; //res用于存储最终结果
vector<int> visited(graph_size+1,0);
que.push({target->val,0}); //将第一个节点放入队列
visited[target->val]=1; //将第一个节点设置为被访问
while(!que.empty()){
auto tmp = que.front(); //取出队列中的第一个节点
que.pop();
if(tmp.second==K) { //如果当前节点的深度已经达到K 将该节点放入res
res.push_back(tmp.first);
continue;
}
for(auto key:graph[tmp.first]){ //将该节点的邻居节点依次放入队列中 并将visited设置为被访问
if(!visited[key]){
que.push({key,tmp.second+1});
visited[key]=1;
}
}
}
cout<<graph_size;
return res;
}
void dfs(TreeNode* root){ //dfs将树转化为图
if(!root)return;
//建立根节点与左子节点 右节点的双向连接 写得有点蠢 见谅
if(root->val>graph_size) graph_size = root->val;
if(root->left) graph[root->val].push_back(root->left->val);
if(root->right) graph[root->val].push_back(root->right->val);
if(root->left) graph[root->left->val].push_back(root->val);
if(root->right) graph[root->right->val].push_back(root->val);
dfs(root->left);
dfs(root->right);
}
};
体会
DFS+BFS，没想到没有爆时间。
使用DFS将树转化为图，之后使用BFS算法从target开始，寻找距离target为K的节点。两个搜索组合即可。
LeetCode133 克隆图
题目
克隆一张无向图，图中的每个节点包含一个 label （标签）和一个 neighbors （邻接点）列表 。
OJ的无向图序列化：
节点被唯一标记。
我们用 # 作为每个节点的分隔符，用 , 作为节点标签和邻接点的分隔符。
例如，序列化无向图 {0,1,2#1,2#2,2}。
该图总共有三个节点, 被两个分隔符 # 分为三部分。
第一个节点的标签为 0，存在从节点 0 到节点 1 和节点 2 的两条边。
第二个节点的标签为 1，存在从节点 1 到节点 2 的一条边。
第三个节点的标签为 2，存在从节点 2 到节点 2 (本身) 的一条边，从而形成自环。
我们将图形可视化如下：
1
/ \
/ \
0 --- 2
/ \
\_/
C++代码
class Solution {
public:
map<int,UndirectedGraphNode*> hash;
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
return dfs(node);
}
UndirectedGraphNode* dfs(UndirectedGraphNode* node) {
if(!node) return node; //如果当前节点为NULL 返回NULL
if(hash.count(node->label)) return hash[node->label]; //如果当前节点被拷贝 返回
UndirectedGraphNode* new_node = new UndirectedGraphNode(node->label); //创建一个新的节点
hash[node->label] = new_node; //将当前节点存在hash中
for(auto tmp:node->neighbors){ //遍历当前节点的邻居节点 对每一个邻居节点dfs
new_node->neighbors.push_back(dfs(tmp));
}
return new_node;
}
};
体会
开始拿到这个题真的愣了一下，其实就是一个无向图的遍历问题，使用DFS算法遍历，每次遍历到一个新的节点，进行深拷贝。
网友评论