3
「算法刷题」深度优先遍历专题汇总（力扣版）
source link: https://magicdeveloperdrl.github.io/2022/06/15/%E7%AE%97%E6%B3%95%E5%88%B7%E9%A2%98-%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%E4%B8%93%E9%A2%98%E6%B1%87%E6%80%BB-%E5%8A%9B%E6%89%A3%E7%89%88.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文记录作者刷题过程中与深度优先遍历相关的题目。
一、岛屿问题
岛屿系列算法问题是经典的面试高频题，岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。如何在二维矩阵中使用 DFS 搜索呢？
我们可以把二维矩阵中的每个点看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的「图」结构，二维矩阵的搜索问题就变成了从某个点出发，向上下左右四个方向进行深度搜索的问题，该dfs函数的框架如下：
// 从(i, j)出发，向相邻四个方向搜索
void dfs(vector<vector<int>>& grid,int i,int j, vector<vector<bool>>& visited) {
int m = grid.length, n = grid[0].length;
// 如果超出索引边界，返回
if (i < 0 || j < 0 || i >= m || j >= n) return;
// 如果已遍历过 (i, j)，返回
if (visited[i][j]) return;
// 进入节点 (i, j)
visited[i][j] = true;// 标记当前点已经访问过
dfs(grid, i - 1, j, visited); // 向上搜索
dfs(grid, i + 1, j, visited); // 向下搜索
dfs(grid, i, j - 1, visited); // 向左搜索
dfs(grid, i, j + 1, visited); // 向右搜索
}
该dfs函数有一个 visited 布尔数组的参数，其目的是防止走回头路，在不同的问题中可以灵活变换，这里放入模板是告诉你二维矩阵需要有一个标记来防止走回头路。
1、求岛屿的数量
200. 岛屿数量（中等难度）
输入一个二维网格grid，其中’1’表示陆地，’0’表示水域，整个网格被水完全包围，陆地格子水平和垂直方向相连（对角线方向不相连）则形成一个岛屿。
点评：
在下述写法中，dfs 函数遍历到值为 '0' 的位置会直接返回，而且搜索一个岛屿后就不会再遍历该岛屿中的”1”，所以我们可以直接省略visited数组，只要把经过的位置都设置为 '0'，就可以起到不走回头路的作用。
注意该题目中是个字符矩阵。
class Solution {
public:
/* 深度优先遍历：
二维遍历每个点，如果当前点是陆地就深度遍历
每个点都以上下左右的方式去做深度递归，搜索过的方格都需要做标记，
*/
int m;
int n;
int numIslands(vector<vector<char>>& grid) {
m = grid.size();
n = grid[0].size();
// 遍历二维数组中的每个点
int res=0;
for(int i = 0; i < m; i++){
for(int j = 0; j <n; j++){
// 如果当前点是陆地，就判断是否形成岛屿（该条件可以删除，但是影响效率）
if(grid[i][j] == '1'){
dfs(grid,i,j);//一定会形成一个岛屿，搜索后就淹没了
res++;
}
}
}
return res;
}
// 从[i,j]向四周搜索，将搜索过的1标记为其他值（0,淹没）
void dfs(vector<vector<char>>& grid,int i,int j){
// 如果当前点超出范围
if(i<0||i>=m||j<0||j>=n) return ;
// 如果当前点是湖水
if(grid[i][j]=='0') return ;
// 如果当前点已遍历过
if(grid[i][j]=='2') return ;
grid[i][j]='2';// 遍历过就标记为2,只要不标记为1（陆地）就行
// 向四周遍历
dfs(grid,i-1,j);// 向左遍历
dfs(grid,i+1,j);// 向右遍历
dfs(grid,i,j-1);// 向上遍历
dfs(grid,i,j+1);// 向下遍历
}
};
1254. 统计封闭岛屿的数目（中等难度）
输入一个二维网格grid，其中0表示陆地，1表示水域，陆地格子水平和垂直方向相连（对角线方向不相连）则形成一个岛屿，封闭岛屿则是其四周完全被水包围。
点评：
该题目中没有假定二维矩阵四周是被海水包围的，所以「靠边的岛屿」理论上可能就不是「封闭岛屿」。
所以在dfs 函数中将「靠边的岛屿」标记下，这样统计的岛屿个数中去除「靠边的岛屿」就是「封闭岛屿」的个数。
class Solution {
public:
/* 该题用0表示土地，1表示水（和其他岛屿问题不同）
所有的岛屿可以分为封闭岛屿和非封闭岛屿，我们已知如何求所有岛屿数量（200题）
封闭岛屿的特点是接触到了边界，所以只要判断当前统计的岛屿是不是封闭岛屿即可
*/
int m;
int n;
int closedIsland(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
// 遍历二维数组中的每个点
int res=0;
for(int i = 0; i < m; i++){
for(int j = 0; j <n; j++){
// 如果当前点是陆地，就扩散
if(grid[i][j] == 0){
bool isClosed=false;
dfs(grid,i,j,isClosed) ;
if(!isClosed) res++;
}
}
}
return res;
}
void dfs(vector<vector<int>>& grid,int i,int j,bool& isClosed){
// 如果当前点超出范围就返回
if(i<0||i>=m||j<0||j>=n) {
isClosed=true;
return ;
}
// 如果当前点不是陆地就返回
if(grid[i][j]==1) return ;
// 如果当前点遍历过就返回
if(grid[i][j]==2) return ;
grid[i][j]=2;// 遍历过就标记为2
// 向四周遍历
dfs(grid,i-1,j,isClosed);// 向左遍历
dfs(grid,i+1,j,isClosed);// 向右遍历
dfs(grid,i,j-1,isClosed);// 向上遍历
dfs(grid,i,j+1,isClosed);// 向下遍历
}
};
1905. 统计子岛屿（中等难度）
点评：
这道题的关键在于，如何快速判断子岛屿？
什么情况下 grid2 中的一个岛屿 B 是 grid1 中的一个岛屿 A 的子岛？
当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。
反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。
那么只要遍历 grid2 中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。
依据这个思路，可以直接写出下面的代码：
class Solution {
public:
/*当岛屿B中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。
反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，
那么岛屿 B就不是岛屿A的子岛*/
int m;
int n;
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
m = grid1.size();
n = grid1[0].size();
for(int i = 0; i < m; i++){
for(int j = 0; j <n; j++){
// 如果岛屿A中陆地在岛屿B中是海水，就淹掉这座小岛
if(grid1[i][j]==0&&grid2[i][j]==1)
dfs(grid2,i,j);//淹掉这座小岛
}
}
// 遍历二维数组中的每个点
int res=0;
for(int i = 0; i < m; i++){
for(int j = 0; j <n; j++){
// 如果当前点是陆地，就判断
if(grid2[i][j] == 1){
dfs(grid2,i,j);
res++;
}
}
}
return res;
}
void dfs(vector<vector<int>>& grid,int i,int j){
// 如果当前点超出范围
if(i<0||i>=m||j<0||j>=n) return ;
// 如果当前点是湖水
if(grid[i][j]!=1) return ;
// 如果当前点已遍历过
if(grid[i][j]==0) return ;
grid[i][j]=0;// 遍历过就标记为0
// 向四周遍历
dfs(grid,i-1,j);// 向左遍历
dfs(grid,i+1,j);// 向右遍历
dfs(grid,i,j-1);// 向上遍历
dfs(grid,i,j+1);// 向下遍历
}
};
694. 不同岛屿的数量（中等难度）
点评：
我们已经会统计矩阵中所有岛屿的数量，也会统计其中「封闭岛屿」的数量，该题是求其中「不同岛屿」的数量。那么如何区分「不同岛屿」？
该题目中的意思是两个岛屿的节点的拓扑结构一样就是相同岛屿（可以直接平移得到），否则就是「不同岛屿」。那么如何表示一个岛屿的拓扑结构呢？这和岛屿的遍历顺序有关。
简单点说，从grid[i][j]出发向四周搜索时，不同的结构在不同的时机返回的顺序不一样，有的结构可能向上搜索一次就直接返回，向下搜索多次才能返回。对于形状相同的岛屿，如果从同一起点出发，dfs 函数遍历的顺序肯定是一样的。
我们可以为dfs函数输入一个字符串参数，其每次向四个方向搜索一次就添加一个不同的字符，这样相同结构的岛屿就会得到一条相同的字符串，否则就是不同的字符串。
将每个岛屿搜索后的字符串放入哈希集合中，哈希集合自动帮我们去重，然后返回哈希集合的大小即可。
class Solution {
public:
int m; // 行数
int n; // 列数
int numDistinctIslands(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
unordered_set<string> set;// 使用哈希集合来存储字符串
// 遍历二维数组中的每个点
for(int i = 0; i < m; i++){
for(int j = 0; j <n; j++){
// 如果当前点是陆地，就扩散
if(grid[i][j] == 1){
string str = "";
dfs(grid,i,j,str);
set.insert(str);
}
}
}
return set.size();
}
void dfs(vector<vector<int>>& grid,int i,int j,string& str){
// 如果当前点超出范围就返回
if(i<0||i>=m||j<0||j>=n)return;
// 如果当前点不是陆地就返回
if(grid[i][j]==0)return;
grid[i][j]=0;// 遍历过就标记为2
// 向四周遍历
dfs(grid,i-1,j,str);// 向左遍历
str += '1';
dfs(grid,i+1,j,str);// 向右遍历
str += '2';
dfs(grid,i,j-1,str);// 向上遍历
str += '3';
dfs(grid,i,j+1,str);// 向下遍历
str += '4';
}
};
2、求岛屿的周长
463. 岛屿的周长（简单难度）
点评：
设计dfs函数从[i,j]出发向四周遍历，返回四个方向边界和湖水的个数，那么就可以得到一个岛屿的周长。
本题的题意是矩阵中始终只会有一个岛屿，我们的代码求的是所有岛屿的周长之和，更进一步：
class Solution {
public:
/* 该题中没有岛内湖，则所有的边长只有两种可能：边界或者湖*/
int m;
int n;
int islandPerimeter(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
int res=0;
// 遍历二维数组中的每个点
for(int i = 0; i < m; i++){
for(int j = 0; j <n; j++){
// 如果当前点是陆地，就扩散
if(grid[i][j] == 1){
res+=dfs(grid,i,j);
}
}
}
return res;
}
// 从[i,j]出发向四周遍历，返回四个方向边界和湖水的个数
int dfs(vector<vector<int>>& grid,int i,int j){
// 如果当前点超出范围,可做周长
if(i<0||i>=m||j<0||j>=n) return 1;
// 如果当前点是湖水，可做周长
if(grid[i][j]==0) return 1;
// 如果当前点已遍历过，不可做周长
if(grid[i][j]==2) return 0;
grid[i][j]=2;// 遍历过就标记为2
// 向四周遍历
int res=0;
res+=dfs(grid,i-1,j);// 向左遍历
res+=dfs(grid,i+1,j);// 向右遍历
res+=dfs(grid,i,j-1);// 向上遍历
res+=dfs(grid,i,j+1);// 向下遍历
return res;
}
};
3、求岛屿的面积
695. 岛屿的最大面积（中等难度）
剑指 Offer II 105. 岛屿的最大面积（中等难度）
点评：
该题目求所有岛屿的最大面积，我们可以用dfs函数求出一个岛屿的面积，最后保存下面积最大的数即可。
改造dfs函数使其返回一个整型面积，显然在grid[i][j]的面积=向上下左右搜索的面积之和+1
注意该题目中的矩阵最大为50阶。
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int res = 0;
// 遍历二维数组中的每个点
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j <grid[0].size(); j++){
// 如果当前点是陆地，就扩散
if(grid[i][j] == 1){
res=max(res,dfs(grid,i,j));//记录每个点遍历的面积的最大值
}
}
}
return res;
}
// 搜索[i,j]向四周扩散后能获得的最大面积
int dfs(vector<vector<int>>& grid,int i,int j){
// 如果当前点超出范围就返回
if(i<0||i>=grid.size()||j<0||j>=grid[0].size()) return 0;
// 如果当前点不是陆地就返回
if(grid[i][j]!=1)return 0;
// 如果当前点已经遍历过,直接返回
if(grid[i][j]==-1)return 0;
grid[i][j]=-1;// 遍历过就标记为-1
// 向四周遍历
int size =1;
size+=dfs(grid,i-1,j);// 向左遍历
size+=dfs(grid,i+1,j);// 向右遍历
size+=dfs(grid,i,j-1);// 向上遍历
size+=dfs(grid,i,j+1);// 向下遍历
return size;
}
};
1020. 飞地的数量（中等难度）
点评：
该题目和「 1254.统计封闭岛屿的数目」非常相似，这题不求封闭岛屿的数量，而是求封闭岛屿的面积总和。
注意该题中 1 代表陆地，0 代表海水。
class Solution {
public:
/*简单讲，本题就是求解所有封闭岛屿的面积，靠近边界的岛屿就不是封闭岛屿*/
int m;
int n;
int numEnclaves(vector<vector<int>>& grid) {
m=grid.size();
n=grid[0].size();
// 遍历二维数组中的每个点
int res=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
bool isClosed=false;
int size=dfs(grid,i,j,isClosed);// 如果是非封闭岛屿则
if(!isClosed) res+=size;
}
}
return res;
}
int dfs(vector<vector<int>>& grid,int i,int j,bool& isClosed){
if(i<0||i>=m||j<0||j>=n){
isClosed=true;
return 0;
}
if(grid[i][j]==0) return 0;
grid[i][j]=0;
int size=1;
size+=dfs(grid,i-1,j,isClosed);
size+=dfs(grid,i+1,j,isClosed);
size+=dfs(grid,i,j-1,isClosed);
size+=dfs(grid,i,j+1,isClosed);
return size;
}
};
4、求矩阵的最长递增路径
329. 矩阵中的最长递增路径（困难难度）
剑指 Offer II 112. 最长递增路径（困难难度）
点评：
该题目求矩阵的最长递增路径，我们可以用dfs函数求出从matrix[i][j]出发向四个方向搜索的最大连续递增长度，显然该长度是四个方向结果的最大值+1。
注意该题目中的矩阵最大为200阶，其题目计算量较大，容易超时，所以我们需要加入一个记忆化搜索，
简单说，我们的visited数组直接保存在matrix[i][j]的最长递增路径，这样面对相同的点就不会重复搜索
class Solution {
public:
/* 从一个格子开始向上下左右搜索，如果四周存在小于它的，遍历过需要标记
那么其最大连续递增长度即为周围小于它的格子的最大连续递增长度中的最大值+1
*/
int longestIncreasingPath(vector<vector<int>>& matrix) {
int res = 0;
vector<vector<int>> visited = vector< vector<int> > (matrix.size(), vector <int> (matrix[0].size()));
// 遍历二维数组中的每个点
for(int i = 0; i < matrix.size(); i++){
for(int j = 0; j <matrix[0].size(); j++){
// 如果当前点没有遍历过
if(visited[i][j]==0){
res=max(res,dfs(matrix,i,j,-1,visited));
}
}
}
return res;
}
int dfs(vector<vector<int>>& matrix,int i,int j,int last,vector<vector<int>>& visited){
// 如果当前点超出范围就返回
if(i<0||i>=matrix.size()||j<0||j>=matrix[0].size()) return 0;
// 如果当前点比上一个点小就返回
if(matrix[i][j]<=last)return 0;
// 如果当前点已经计算过，就直接返回最大路径
if(visited[i][j] != 0) return visited[i][j];
// 向四周遍历,取最大方向
int size =0;
int tmp=matrix[i][j];
size=max(size,dfs(matrix,i-1,j,tmp,visited));// 向左遍历
size=max(size,dfs(matrix,i+1,j,tmp,visited));// 向右遍历
size=max(size,dfs(matrix,i,j-1,tmp,visited));// 向上遍历
size=max(size,dfs(matrix,i,j+1,tmp,visited));// 向下遍历
// 标记当前点已经遍历过
visited[i][j]=size+1;
return visited[i][j];
}
};
5、在矩阵中匹配字符串
79. 单词搜索（中等难度）
剑指 Offer 12. 矩阵中的路径（中等难度）
点评：
该题目求字符矩阵中是否存在一个字符串，我们可以用dfs函数求出从board[i][j]出发向四个方向搜索如果有一个方向匹配即可，显然dfs函数要传入字符串word和它的当前匹配索引k。
注意本题中求一个点board[i][j]后需要回溯，因为其遍历过的点之后可能还需要遍历
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
// 遍历二维数组中的每个点
for(int i=0;i<board.size();++i){
for(int j=0;j<board[0].size();++j){
// 如果当前点满足测试条件
if(board[i][j]==word[0]){
// 遍历测试
if(dfs(board,word,i,j,0)) return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board,string& word,int i,int j,int k){
// 如果当前点超出范围
if(k==word.size()) return true;
// 如果当前点超出范围
if(i<0||i>=board.size()||j<0||j>=board[0].size()) return false;
// 如果当前点不匹配字符
if(board[i][j]!=word[k]) return false;
// 进入
char tmp=board[i][j];
board[i][j]='0';// 遍历过就标记为0
// 向四周遍历
bool res=dfs(board,word,i-1,j,k+1)||// 向左遍历
dfs(board,word,i+1,j,k+1)||// 向右遍历
dfs(board,word,i,j-1,k+1)||// 向上遍历
dfs(board,word,i,j+1,k+1);// 向下遍历
// 回溯
board[i][j]=tmp;// 下一个点还可以遍历
return res;
}
};
二、二叉树问题
1、二叉树的序列化和反序列化
剑指 Offer 37. 序列化二叉树（困难难度）
297. 二叉树的序列化与反序列化（困难难度）
二叉树的序列化：输入一个二叉树，输出其层序遍历输出的字符串
二叉树的反序列化：输入一个字符串，输出其构造的二叉树
点评
二叉树的序列化有先序、中序、后序和层序，但是二叉树的反序列化不支持中序遍历（无法确定根节点位置）。
基于先序遍历的序列化和反序列化：
//序列化
string serialize(TreeNode* root){
string str="";
dfs(root,str);
return str;
}
void dfs(TreeNode* root,string& str){
if(root==nullptr){
str+="null,";
return;
}
str+=to_string(root->val)+",";
dfs(root->left,str);
dfs(root->right,str);
}
// 反序列化
TreeNode* deserialize(string data){
if(data.length()==0) return nullptr;
// 切割字符串
vector<string> str;
stringstream ss(data);
string t;
while(getline(ss,t,',')){
str.push_back(t);
}
// 构造二叉树
return dedfs(str,0);
}
TreeNode* dedfs(vector<string>& nodes，int i){
// 终止条件
if(i>=nodes.size()) return nullptr;
// 处理节点
if(nodes[i]=="null") return nullptr;
TreeNode* root=new TreeNode(stoi(nodes[i]));
i++;
// 递归搜索
root->left=dedfs(nodes,i);
root->right=dedfs(nodes,i);
return root;
}
基于层序遍历的序列化和反序列化：
string serialize(TreeNode* root) {
if(root==nullptr) return "";
string res="";
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
// 出栈
TreeNode* cur=que.front();
que.pop();
// 处理
if(cur==nullptr) res+="null,";
else{
res+=to_string(cur->val)+",";
// 入栈
que.push(cur->left);
que.push(cur->right);
}
}
return res;
}
TreeNode* deserialize(string data) {
if(data.length()==0) return nullptr;
// 切割字符串
vector<string> str;
stringstream ss(data);
string t;
while(getline(ss,t,',')){
str.push_back(t);
}
// 构建二叉树
queue<TreeNode*> que;
if(str[0]=="null") return nullptr;
TreeNode* root=new TreeNode(stoi(str[0]));
que.push(root);
for(int i=1;i<str.size();){
// 获取根节点
TreeNode* cur=que.front();
que.pop();
// 添加左节点
if(str[i]=="null") cur->left=nullptr;
else{
cur->left=new TreeNode(stoi(str[i]));
que.push(cur->left);
}
++i;
// 添加右节点
if(str[i]=="null") cur->right=nullptr;
else{
cur->right=new TreeNode(stoi(str[i]));
que.push(cur->right);
}
++i;
}
return root;
}
2、求二叉树的路径
257. 二叉树的所有路径（简单难度）
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
class Solution {
public:
vector<string> res;
void dfs(TreeNode* root,string path){
// 如果节点为空,返回
if(root==nullptr) return;
path+=to_string(root->val);//添加当前节点
//如果是叶子节点,说明一条路径结束,递归返回
if(root->left==nullptr&&root->right==nullptr){
res.push_back(path);
return;
}
if(root->left){
dfs(root->left,path+"->");
}
// 进入该节点，尝试搜索右节点
if(root->right){
dfs(root->right,path+"->");
}
}
vector<string> binaryTreePaths(TreeNode* root) {
dfs(root, "");
return res;
}
};
129. 求根节点到叶节点数字之和（中等难度）
剑指 Offer II 049. 从根节点到叶节点的路径数字之和（中等难度）
class Solution {
public:
vector<string> res;
void dfs(TreeNode* root,string path){
// 如果节点为空,返回
if(root==nullptr) return;
path+=to_string(root->val);//添加当前节点
// 如果是叶节点就是一条路径
if(root->left==nullptr&&root->right==nullptr){
res.push_back(path);
return;
}
// 进入该节点，尝试搜索左节点
if(root->left)dfs(root->left,path);
// 进入该节点，尝试搜索右节点
if(root->right)dfs(root->right,path);
}
int sumNumbers(TreeNode* root) {
dfs(root,"");
int sum=0;
for(string s:res){
sum+=stoi(s);
}
return sum;
}
};
124. 二叉树中的最大路径和（困难难度）
路径定义为从树中的任意节点出发，父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
点评：
该题的难点在于路径的方向不固定，起点可以是任意节点，终点也可以说任意节点，然后返回路径和。
传统的二叉树的路径一般是从根节点到叶节点。
那么如何求任意节点到任意节点的最大路径和呢？
我们考虑一个最简单的二叉树，left表示左节点为根节点的子树的最大路径和，right表示右节点为根节点的子树的最大路径和。
那么对于root根的二叉树来讲，其形成的路径可以能有：
left-root-right（条件：left>0,right>0）
left-root（条件：left>0,right<=0）
root-right（条件：left<=0,right>0）
root（条件：left<=0,right<=0）
假设我们的递归函数dfs()返回以根节点root为子树的最大路径和，那么
int left=dfs(node->left);
int right=dfs(node->left);
class Solution {
public:
int maxSum = INT_MIN;// 记录的最大值
// 返回以node为根的左右子树中的最大和
int dfs(TreeNode* node) {
// 如果节点为空，返回
if (node == nullptr) return 0;
// 进入该节点
// 该节点尝试向左,left表示左子树最大的路径和，最小为0，如果设为0则放弃左子树为路径
int left = max(0, dfs(node->left));
// 该节点尝试向右，right表示右子树最大的路径和，最小为0，如果设为0则放弃左子树为路径
int right = max(0, dfs(node->right));
//假如以left-root-left为路径，得到路径和：
int priceNewpath = node->val + left + right;
// 如果该路径和最大则记录
maxSum = max(maxSum, priceNewpath);
// 该节点最终选择左还是右取决于左右子节点的最大贡献值
return max(node->val+left, node->val+right);
}
int maxPathSum(TreeNode* root) {
dfs(root);
return maxSum;
}
};
113. 路径总和 II
剑指 Offer 34. 二叉树中和为某一值的路径
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
// 递归函数不需要返回值，因为我们要遍历整个树
void traversal(TreeNode* cur, int count) {
// 如果是叶子节点，且为0,添加到结果中并返回
if (!cur->left && !cur->right && count == 0) {
result.push_back(path);
return;
}
// 如果是叶子节点，不为0,直接返回
if (!cur->left && !cur->right) return ;
// 如果是左节点存在，递归左节点
if (cur->left) {
path.push_back(cur->left->val);
count -= cur->left->val;
traversal(cur->left, count); // 递归
count += cur->left->val; // 回溯
path.pop_back(); // 回溯
}
// 如果右节点存在，递归右节点
if (cur->right) { // 右 （空节点不遍历）
path.push_back(cur->right->val);
count -= cur->right->val;
traversal(cur->right, count); // 递归
count += cur->right->val; // 回溯
path.pop_back(); // 回溯
}
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if (root == NULL) return result;
path.push_back(root->val); // 把根节点放进路径
traversal(root, targetSum - root->val);
return result;
}
};
437. 路径总和 III（中等难度）
方法一：递归法
class Solution {
public:
// 查找包含root节点并且和为sum的路径个数
int findPath(TreeNode* root,int sum){
int result=0;
if(root==nullptr) return result;
// 如果加上root，和满足则结果+1
if(sum==root->val) result+=1;
// 查找包含root左节点
result+=findPath(root->left,sum-root->val);
// 查找包含root右节点
result+=findPath(root->right,sum-root->val);
return result;
}
// 查找包含root/不包含root并且和为targetSum的路径个数
int pathSum(TreeNode* root, int targetSum) {
int result=0;
if(root==nullptr) return result;
result+=findPath(root,targetSum);// 查找包含root节点并且和为sum的路径个数
result+=pathSum(root->left,targetSum);// 查找包含root节点并且和为sum的路径个数
result+=pathSum(root->right,targetSum);
return result;
}
};
方法二：前缀和+递归法
class Solution {
public:
unordered_map<long long, int> dict; //<[0,b]的前缀和，出现次数>
int res = 0;
// pathSum：[a,root]的目标和;curSum：[0,root]的前缀和
void dfs(TreeNode* root,int pathSum,int curSum){
if (root == nullptr) return;
curSum += root->val; //当前节点的前缀和[0,b]
// [0,b]的前缀和-[a,b]的前缀和=[0,a-1]的前缀和，哈希表中是否存在
if (dict.count(curSum - pathSum)){
res += dict[curSum - pathSum];//
}
// 将[0,b]的前缀和存入哈希表，遍历是否存在满足要求的子树
dict[curSum]++;
dfs(root->left,pathSum, curSum);//查看是否存在root的左节点的
dfs(root->right,pathSum, curSum);
// 当子树结束时，应当把子树从哈希表中移除 (回溯：将一切复原，然后结束)。
dict[curSum]--;
}
// 查找包含root/不包含root并且和为targetSum的路径个数
int pathSum(TreeNode* root, int targetSum) {
// 注意 前缀和中, [a, b] = [0, b] - [0, a-1] 。
// 对于包含根节点的路径，是无法找到 a-1 的。所以需要一个虚拟根节点。
dict[0] = 1;
dfs(root,targetSum, 0); //targetSum视为[a,b]区间的和
return res;
}
};
404. 左叶子之和（简单难度）
class Solution {
public:
int preOrder(TreeNode* root,bool isleft){
int result=0;
// 如果是空节点，返回0
if(root==NULL) return 0;
// 如果是左叶子，返回其值
if(isleft&&root->left==NULL&&root->right==NULL) return root->val;
result+=preOrder(root->left,true);// 递归左节点
result+=preOrder(root->right,false);// 递归右节点
return result;
}
int sumOfLeftLeaves(TreeNode* root) {
return preOrder(root,false);
}
};
863. 二叉树中所有距离为 K 的结点（中等难度）
class Solution {
unordered_map<int, TreeNode*> parents;// 当前节点值-父节点
void findParents(TreeNode* node) {
if(node==nullptr) return;
if (node->left) {
parents[node->left->val] = node;//最节点的父节点是node
findParents(node->left);
}
if (node->right) {
parents[node->right->val] = node;//右节点的父节点是node
findParents(node->right);
}
}
vector<int> ans;
void findAns(TreeNode* node, TreeNode* from, int depth, int k) {
// 如果当前节点为空，返回
if (node == nullptr) return;
// 如果当前深度==k，返回并添加结果
if (depth == k) {
ans.push_back(node->val);
return;
}
// 搜索3个方向，from是搜索来源方向
if (node->left != from) findAns(node->left, node, depth + 1, k);// 左节点
if (node->right != from) findAns(node->right, node, depth + 1, k);// 右节点
if (parents[node->val] != from) findAns(parents[node->val], node, depth + 1, k);// 父节点
}
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
// 从root出发 DFS，记录每个结点的父结点
findParents(root);
// 从 target 出发 DFS，寻找所有深度为 k 的结点
findAns(target, nullptr, 0, k);
return ans;
}
};
3、自底向上寻找祖先
剑指 Offer 68 - II. 二叉树的最近公共祖先（简单难度）
236. 二叉树的最近公共祖先（中等难度）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//如果当前节点为空，直接返回空
if(root==NULL) return NULL;
//如果当前节点值和p或者q中的一个相等，则返回当前节点
if(p->val==root->val||q->val==root->val)return root;
//递归调用
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
//如果左子树和右子树分别存在p和q
if (left != NULL && right != NULL)return root;
//如果右子树存在p和q
if (left == NULL && right != NULL)return right;
//如果左子树存在p和q
if (left != NULL && right == NULL) return left;
return NULL;
}
};
4、层序遍历
662. 二叉树最大宽度（中等难度）
class Solution {
public:
/*空节点下还可以挂载空节点,无法通过常规的层序遍历来为空节点保留子节点
给每个节点添加一个编号，通过编号来记录每层的宽度，但是这个编号可能会非常大
由于官方更新了测试用例，导致用原本二叉树的val记录编号（int型）会造成溢出。*/
int widthOfBinaryTree(TreeNode* root) {
int res=0;
queue<pair<TreeNode *, long long>> que; //队列记录二叉树的结点和一个对应的long long型编号
if(root==nullptr) return res;
que.push(make_pair(root, 0)); //根节点入队，并记录对应编号
while(!que.empty()){
int size=que.size();
int start = 0, end = 0;
// 从左到右遍历每一行
for(int i=0;i<size;++i){
// 出队
TreeNode* curNode = que.front().first;
long long curId = que.front().second;
que.pop();
// 记录当前行第一个和最后一个节点的编号
if (i == 0) start = curId;
if (i == size - 1) end = curId;
curId -= start; //缩小编号索引，以每层第一个结点的值为偏移值，保持每层结点之间的相对关系，缩小索引
// 入队
if(curNode->left){
que.push(make_pair(curNode->left, curId*2));
}
if(curNode->right){
que.push(make_pair(curNode->right, curId*2+1));
}
}
res=max(res, (int)(end-start+1));
}
return res;
}
};
958. 二叉树的完全性检验（中等难度）
给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
queue<TreeNode*> que;
que.push(root);
bool end=false;// 是否遍历完所有的非空节点
while(!que.empty()){
int size=que.size();
// 从左到右遍历每一行
for(int i=0;i<size;++i){
// 出队
TreeNode* curNode = que.front();
que.pop();
// 第一次遇到null时end变成true，如果之后的所有节点都是 null，则说明是完全二叉树
if(curNode==nullptr) end = true;// 第一次遇到 null 时 end 变成 true
else{
// end 为 true 时遇到非空节点说明不是完全二叉树
if (end) return false;
// 入队
que.push(curNode->left);
que.push(curNode->right);
}
}
}
return true;
}
};
三、括号问题
22. 括号生成（中等难度）
剑指 Offer II 085. 生成匹配的括号（中等难度）
面试题 08.09. 括号（中等难度）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
点评：
由于有效的括号字符串中左括号数量一定等于右括号数量，所以每个括号组合中一定有n个左括号和n个右括号。
我们可以尝试放入一个左括号或右括号来进行回溯遍历，终止条件是：
1、从左向右添加括号字符，当右括号数量大于左括号数量时一定不符合
2、左右括号数量任何一个超过n就一定不符合
3、左括号数量==右括号数量==n时就一定找到了一个合法的组合
class Solution {
public:
vector<string> res;
string path;
// 左括号的数量、右括号的数量
void dfs(int n,int left,int right){
if(right>left) return;// 从左向右添加括号字符，当右括号多的时候就一定不符合
if(left>n||right>n) return;// 如果有某个括号超过一半，则一定不是合法的
// 如果左右括号恰好都为n
if(left==n&&right==n){
res.push_back(path);
return ;
}
// 先尝试放入左括号
path.push_back('(');
dfs(n,left+1,right);
path.pop_back();
// 再尝试放入右括号
path.push_back(')');
dfs(n,left,right+1);
path.pop_back();
}
vector<string> generateParenthesis(int n) {
dfs(n,0,0);
return res;
}
};
301. 删除无效的括号（困难难度）
输入一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。返回所有可能的结果。答案可以按 任意顺序 返回。
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
点评
这道题和1249的区别在于，1249题只需要返回一种最少删除无效括号的情况就行，我们只要能找出一种所有不匹配的括号位置，将其删除即可，这些不匹配的括号位置依赖于我们从左向右搜素的顺序。
该题要返回所有最少删除的括号数量的情况，我们借助栈从左向右查找不匹配顺序只能找到其中一种情况；
我们可以使用回溯，先统计字符串中所有的要删除的左右括号数量
对每个左括号或者右括号字符都尝试删除，然后搜索所有情况，显然终止条件是：
1、剩余的要删除的括号数量>字符串剩余数量
2、如果左括号和右括号正好删够，并且是合法字符串
class Solution {
public:
vector<string> res;
void dfs(string& str, int start, int lremove, int rremove) {
// 如果剩余的字符无法满足去掉的数量要求，直接返回
if (lremove + rremove > str.size()) return;
// 如果左括号和右括号正好删够，并且是合法字符串
if (lremove == 0 && rremove == 0&&isValid(str)) {
res.push_back(str);
return;
}
// 每个节点从str的[start,:)，尝试分别删除左右括号
for (int i = start; i < str.size(); i++) {
// 如果同一层分支相同，则直接跳过
if (i>start && str[i] == str[i - 1]) continue;
// 尝试去掉一个左括号
if ( str[i] == '(') {
string tmp=str.substr(0, i)+str.substr(i + 1);
dfs(tmp, i, lremove - 1, rremove);
}
// 尝试去掉一个右括号
if ( str[i] == ')') {
string tmp=str.substr(0, i)+str.substr(i + 1);
dfs(tmp, i, lremove, rremove - 1);
}
}
}
vector<string> removeInvalidParentheses(string s) {
int lremove = 0;// 需要删除的左括号数量
int rremove = 0;// 需要删除的右括号数量
// 遍历字符串，统计要删除的左括号和右括号的数量
for (char c : s) {
if (c == '(') lremove++;
else if (lremove != 0&&c == ')') lremove--;
else if (lremove == 0&&c == ')') rremove++;// 要删除的右括号
}
dfs(s, 0, lremove, rremove);
return res;
}
inline bool isValid(const string & s) {
int cnt = 0;
// 判断括号字符串是否合法
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
cnt++;
} else if (s[i] == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
};
四、有向图问题
207. 课程表（中等难度）
class Solution {
public:
/*该题本质是一个有向图，我们可以创建一个有向图，
然后从图中的任意一个节点出发开始搜索，如果搜索中没有遇到环（相互依赖的课程）
则本次搜索是复合要求的，继续从下一个节点开始搜索，直至搜索过所有节点
在该过程中，我们需要避免一个节点被重复搜索，所以图中的每个节点可以分为三种状态：
「未搜索」：该节点还没有被搜索过，每个节点的初始状态，设为0
「搜索中」：该节点正在被其他节点出发的搜索过程搜索，但是还没有返回，
如果在搜索中遇到了这样的节点状态，则说明遇到环，即从不同节点出发搜索到了同一个节点
「已搜索」：该节点被从其他节点出发的搜索过程搜索过且没有遇到环，本次搜索可直接跳过*/
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> edges(numCourses,vector<int>());// 有向图
vector<int> visited(numCourses,0);// 0「未搜索」、1「搜索中」、2「已搜索」
// 遍历课程表,记录修完第i门课的所有相邻课程（学完i可以继续学哪些课）
for (const auto& info: prerequisites) edges[info[1]].push_back(info[0]);
// 遍历每一门课，尝试进行搜索
for (int i = 0; i < numCourses; ++i) {
// 如果课程为「未搜索」,则搜索
if (visited[i]==0) {
if(dfs(i,edges,visited))return false;// 如果本次搜索遇到环，则立即返回
}
}
return true;
}
// 定义：从课程u出发，搜索其所有的相邻课程v，如果遇到环返回true
bool dfs(int u,vector<vector<int>>& edges, vector<int>& visited) {
visited[u] = 1; // 标记当前课程u为搜索中
// 遍历当前课程u的每一个相邻课程v
for (int v: edges[u]) {
// 如果相邻课程v为「未搜索」
if (visited[v] == 0) {
if(dfs(v,edges,visited))return true;// 如果本次搜索遇到环，则立即返回
}
// 如果相邻课程v为「搜索中」,说明找到一个环,立即返回
else if (visited[v] == 1) return true;
// 如果相邻课程v为「已完成」，不需要搜索（可省略本条件）
else if (visited[v] == 2) continue;
}
visited[u] = 2;// 标记课程u为「已搜索」
return false; // 该课程搜索时没遇到环
}
};
210. 课程表 II（中等难度）
class Solution {
public:
vector<int> res;
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> edges(numCourses,vector<int>());// 有向图
vector<int> visited(numCourses,0);// 0「未搜索」、1「搜索中」、2「已搜索」
// 遍历课程表,记录修完第i门课的所有相邻课程（学完i可以继续学哪些课）
for (const auto& info: prerequisites) edges[info[1]].push_back(info[0]);
// 遍历每一门课，尝试进行搜索
for (int i = 0; i < numCourses; ++i) {
// 如果课程为「未搜索」,则搜索,符合条件会加入res
if (visited[i]==0) {
if(dfs(i,edges,visited))return {};// 如果本次搜索遇到环，则立即返回
}
}
reverse(res.begin(),res.end());
return res;
}
// 定义：从课程u出发，搜索其所有的相邻课程v，如果遇到环返回true
bool dfs(int u,vector<vector<int>>& edges, vector<int>& visited) {
visited[u] = 1; // 标记当前课程u为搜索中
// 遍历当前课程u的每一个相邻课程v
for (int v: edges[u]) {
// 如果相邻课程v为「未搜索」
if (visited[v] == 0) {
if(dfs(v,edges,visited))return true;// 如果本次搜索遇到环，则立即返回
}
// 如果相邻课程v为「搜索中」,说明找到一个环,立即返回
else if (visited[v] == 1) return true;
// 如果相邻课程v为「已完成」，不需要搜索（可省略本条件）
else if (visited[v] == 2) continue;
}
visited[u] = 2;// 标记课程u为「已搜索」
res.push_back(u);
return false; // 该课程搜索时没遇到环
}
};
五、区间问题
312. 戳气球（困难难度）
class Solution {
public:
/* 该题使用普通的回溯搜索,尝试每一层戳破第i个气球，时间复杂度是O(n!)
方法一：回溯搜索，时间复杂度O(n!)，超时
方法二：基于分治法的记忆化搜索，时间复杂度O(log(n))
方法三：动态规划法
*/
// 方法一：回溯搜索，时间复杂度是O(n!)
int maxCoins1(vector<int>& nums) {
int len=nums.size();
int maxCoin=0;
dfs(nums,0,len,0,maxCoin);
return maxCoin;
}
void dfs(vector<int>& nums, int y, int length, int beforeCoins,int& maxCoin) {
//回归条件
if (y==length) {
if (beforeCoins>maxCoin) maxCoin = beforeCoins;
else return;
}
for (int i = 0; i < length; i++) {
//略过已经戳破的气球
if (nums[i] == -1) continue;
//标记已经戳破的气球
int temp = nums[i];
nums[i] = -1;
//获取上一个气球的数字
int before = i - 1;
int beforeNum = 0;
while(before>-1&&nums[before]==-1) before--;
if (before < 0) beforeNum = 1;
else beforeNum = nums[before];
//获取下一个气球的数字
int next = i + 1;
int nextNum = 0;
while(next<length&&nums[next]==-1) next++;
if (next>length-1) nextNum = 1;
else nextNum = nums[next];
//计算戳破当前气球的coin
int tempCoin = temp * nextNum * beforeNum;
//递归进行下一戳
dfs(nums, y+1, length,beforeCoins+tempCoin,maxCoin);
//回溯尝试其它戳法
nums[i] = temp;
}
}
// 方法二：记忆化搜索
int maxCoins(vector<int>& nums) {
nums.insert(nums.begin(),1);
nums.push_back(1);
int len=nums.size();
vector<vector<int>> dp(len,vector<int>(len,-1));
return dfs(nums,0,len-1,dp);
}
// 定义：在左开右开区间（left,right）戳破所有气球获得的最大金币数
int dfs(vector<int>& nums,int left,int right,vector<vector<int>>&dp){
if(left==right-1) return 0;// 如果区间为空，返回0
if(dp[left][right]!=-1) return dp[left][right];// 如果区间已经搜索过，直接返回
int max_v=0;//
// 尝试戳破（left,right）中的第i个气球
for(int i=left+1;i<=right-1;++i){
int temp=dfs(nums,left,i,dp)+dfs(nums,i,right,dp)+nums[i]*nums[left]*nums[right];
dp[left][right]=max(max_v,temp);
}
dp[left][right]=max_v;
return max_v;
}
// 方法三：动态规划法
int maxCoins3(vector<int>& nums) {
nums.insert(nums.begin(),1);
nums.push_back(1);
int len=nums.size();
//dp[left][right] 定义：在左开右开区间（left,right）戳破所有气球获得的最大金币数
vector<vector<int>> dp(len,vector<int>(len,0));
for(int l=2;l<=len;l++){
for(int left=0;left<=len-l;left++){
int right=left+l-1;
// 尝试戳破（left,right）中的第i个气球
for(int k=left+1;k<=right-1;k++){
int temp=dp[left][k]+dp[k][right]+nums[left]*nums[k]*nums[right];
dp[left][right] = max(dp[left][right],temp);
}
}
}
return dp[0][len-1];
}
};
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK