树的层序遍历

树的层序遍历 推广到图就是广度优先搜索 ,它是借助队列 这个数据结构实现的。

如图,我们先将根节点放入队列中;然后队首的节点出队,将其左右孩子入队;重复这个操作(迭代),直到队列为空时,遍历结束

合并二叉树

题目

给你两棵二叉树: root1 和 root2 。

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例1: 输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出:[3,4,5,5,4,null,7]

分析

这是一道比较简单的题,但是如果我们把能想到的所有方法都实现一遍,或许这道题就没有那么简单了。题目要求我们合并两棵二叉树,我们要做的就是同时遍历这两棵树:如果两棵树对应位置的结点同时存在,则值相加;如果只有一边存在结点,则将存在结点的那棵树的对应结点挂到新树上

而遍历一棵树的方法有四种,包括前中后三序遍历层序遍历 。而前面三种遍历既可以递归实现,也可以用栈实现。

递归实现

二叉树是一种很适合递归的数据结构,因为它本身的定义 就是递归的:

一棵树或为空树,或是由一个根节点加上两棵分别称为左子树或右子树的互不相交的二叉树组成。

而对一棵树进行深度优先遍历的模板也很简单,以先序遍历为例:

1
2
3
4
5
6
7
8
9
void preorder(TreeNode* root){
//递归的终止条件
if(root==nullptr) return;
visit();//先序
preorder(root->left);
//visit() //中序
preorder(root->right);
//visit() //后序
}

所以,需要对树进行遍历时我们可以首先思考递归的方法。

对于这道题,我们同时对两棵树进行遍历,递归的终止条件是有一棵树的结点为空,此时返回不为空的结点,就可以将它挂到新树上。当两棵树的结点都不为空时,值相加赋给新树的结点;这里的访问操作visit()就是将结点的值相加,所以可以将这个操作放到不同的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr || root2==nullptr)
return root1==nullptr?root2:root1;
root1->val+=root2->val;//先序
root1->left=mergeTrees(root1->left,root2->left);
// root1->val+=root2->val;//中序
root1->right=mergeTrees(root1->right,root2->right);
// root1->val+=root2->val;//后序
return root1;
}
};
judge

栈实现

既然可以递归那么就可以用栈。我们规定先访问左子树,再访问右子树,那么压栈的顺序就是先将结点的右孩子压入栈中,再将左孩子入栈。这样的结果就是前序遍历:

两棵树同时遍历同理,我们使用一个栈来存储结点对pair<TreeNode*,TreeNode*>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr||root2==nullptr)
return root1==nullptr?root2:root1;
stack<pair<TreeNode*,TreeNode*> > stk;
stk.emplace(root1,root2);
while(!stk.empty()){
TreeNode* t1=stk.top().first;
TreeNode* t2=stk.top().second;
stk.pop();
t1->val+=t2->val;
if(t1->right!=nullptr&&t2->right!=nullptr)
stk.emplace(t1->right,t2->right);
else if(t2->right!=nullptr)
t1->right=t2->right;
if(t1->left!=nullptr&&t2->left!=nullptr)
stk.emplace(t1->left,t2->left);
else if(t2->left!=nullptr)
t1->left=t2->left;
}
return root1;
}
};
judge

队列实现

我们使用层序遍历的方式来遍历二叉树,使用队列即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr||root2==nullptr)
return root1==nullptr?root2:root1;
queue<TreeNode*> que;
que.push(root1);
que.push(root2);
while(!que.empty()){
TreeNode* t1=que.front();
que.pop();
TreeNode* t2=que.front();
que.pop();
t1->val+=t2->val;
if(t1->left!=nullptr&&t2->left!=nullptr){
que.push(t1->left);
que.push(t2->left);
}
else if(t1->left==nullptr&&t2->left!=nullptr)
t1->left=t2->left;

if(t1->right!=nullptr&&t2->right!=nullptr){
que.push(t1->right);
que.push(t2->right);
}
else if(t1->right==nullptr&&t2->right!=nullptr)
t1->right=t2->right;
}
return root1;
}
};
judge


填充每个节点的下一个右侧节点指针

二叉树结点定义:

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
题目

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

示例: 输入:root = [1,2,3,4,5,6,7] 输出:[1,#,2,3,#,4,5,6,7,#]

层序遍历

可以看到,next指针都是按层连接的,所以我们很自然地就会想到层序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
Node* connect(Node* root) {
if(root==nullptr) return root;
queue<Node*> que;
que.push(root);
while(!que.empty()){
int len=que.size();
for(int i=0;i<len;i++){
Node* node=que.front();
que.pop();
if(i<len-1) node->next=que.front();
if(node->left!=nullptr){
que.push(node->left);
que.push(node->right);
}
}
}
return root;
}
};

遍历队列时按层连接next指针即可。要注意的是每层连接的指针数为结点数-1,所以还要添加一个判断条件if(i<len-1)

judge

递归实现

其实,在不是那么熟悉,或者是没有第一时间想到层序遍历的情况下,应该会先想到递归的方法,因为这更符合直觉。

分析题意可以发现:对于一个结点,我们对它的操作是将它的左孩子指向右孩子;如果该结点的next指针不为空的话,还要将右孩子指向右侧结点的左孩子。每个结点的操作都是如此,所以可以使用递归实现,结束的终止条件就是该结点的下一层为空。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
Node* connect(Node* root) {
if(root==nullptr||root->left==nullptr) return root;
else root->left->next=root->right;
if(root->next!=nullptr)
root->right->next=root->next->left;
connect(root->left);
connect(root->right);
return root;
}
};
judge


多源最短路径

《数据结构与算法》 这门课程中,我们学过单源最短路径Dijkestra算法 ,也学过多源最短路径Floyd算法 ——这两种算法是针对带权图的一般性的做法,如果是无权图,或者说每一步权值都是1,那么就可以使用广度优先搜索

01矩阵

题目

给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例: 输入:mat = [[0,0,0],[0,1,0],[1,1,1]] 输出:[[0,0,0],[0,1,0],[1,2,1]]

分析

看到这道题,一般的想法是遍历数组,如果是1,那么就对其进行BFS,计算到最近的0的距离。

但是,如果我们再分析一下这种方法的时间复杂度就会发现,这其实是一种极不可取的做法!那么我们换个角度,对所有的0进行多源BFS。每进行一轮BFS,步数加一。

使用flag数组

过程图如下:

  1. 遍历矩阵,找到其中的0并入队,同时将其dist修改为0,flag修改为T;
  2. 搜索队列中元素的上下左右四个方向,如果发现了1,且其flag=F,即还没有遍历到这个元素,那么就将dist相应位置更新为源点+1,flag更新为T;(BFS)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int row=mat.size(),column=mat[0].size();
pair<int,int> dir[4]={{-1,0},{0,-1},{1,0},{0,1}};
vector<vector<int>> dist(row, vector<int>(column,row));
vector<vector<bool>> flag(row, vector<bool>(column,false));
queue<pair<int, int>> que;
for(int i=0;i<row;i++)
for(int j=0;j<column;j++){
if(mat[i][j]==0){
dist[i][j]=0;
flag[i][j]=true;
que.emplace(i,j);
}
}
while(!que.empty()){
auto p=que.front();
que.pop();
for(auto i:dir){
int r=p.first+i.second;
int c=p.second+i.first;
if(r<0||r>=row||c<0||c>=column) continue;
if(flag[r][c]==false){
dist[r][c]=dist[p.first][p.second]+1;
flag[r][c]=true;
que.emplace(r,c);
}
}
}
return dist;
}
};
judge

看起来效果并不是很理想。进一步分析发现,falg数组完全是多余的!

不用falg数组

从这个图可以很好地发现,当dist是无穷或一个很大的数时,对应的元素就没有遍历过。它和flag的更新时同步的,所以我们根据dist来判断即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int row=mat.size(),column=mat[0].size();
pair<int,int> dir[4]={{-1,0},{0,-1},{1,0},{0,1}};
vector<vector<int>> dist(row, vector<int>(column,10000));
queue<pair<int, int>> que;
for(int i=0;i<row;i++)
for(int j=0;j<column;j++){
if(mat[i][j]==0){
dist[i][j]=0;
que.emplace(i,j);
}
}
while(!que.empty()){
auto [i,j]=que.front();
que.pop();
for(auto d:dir){
int r=i+d.second;
int c=j+d.first;
if(r<0||r>=row||c<0||c>=column) continue;
if(dist[r][c]==10000){
dist[r][c]=dist[i][j]+1;
que.emplace(r,c);
}
}
}
return dist;
}
};
judge

这个做法的效率已经不错了,但是还有更优的做法——动态规划。不过我现在还并不想做DP问题,这个方法之后再说吧……


腐烂的橘子

题目

在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:

  • 值 0 代表空单元格;
  • 值 1 代表新鲜橘子;
  • 值 2 代表腐烂的橘子。

每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。

示例: 输入:grid = [[2,1,1],[1,1,0],[0,1,1]] 输出:4

分析: 这道题和上一道题不能说是完全相同只能说是一模一样。腐烂的橘子就是源点,然后进行多源BFS,每次都将矩阵中的1(新鲜橘子)更新为0(腐烂橘子),同时记录BFS的层数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int row=grid.size(),column=grid[0].size(),fresh=0,round=0;
pair<int,int> dir[4]={{-1,0},{0,-1},{1,0},{0,1}};
queue<pair<int,int>> que;
for(int i=0;i<row;i++)
for(int j=0;j<column;j++){
if(grid[i][j]==2) que.emplace(i,j);
if(grid[i][j]==1) fresh++;
}
while(fresh>0&&!que.empty()){
int len=que.size();
for(int k=0;k<len;k++){
auto [i,j]=que.front();
que.pop();
for(auto d:dir){
int r=i+d.second,c=j+d.first;
if(r<0||r>=row||c<0||c>=column) continue;
if(grid[r][c]==1){
fresh--;
grid[r][c]=2;
que.emplace(r,c);
}
}
}
round++;
}
if(fresh>0) return -1;
return round;
}
};

judge