本文章记录贪心法的一些 LeetCode 题目，是我学习b站小象学院视频教程所做笔记，文末注明教程出处。侵删 ¯\_( ͡° ͜ʖ ͡°)_/¯
LeetCode [113] 路径总和Ⅱ
题目描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[ [5,4,11,2], [5,8,4,5] ]
算法思想
其实就很简单的二叉树搜索吧，把先序的深度遍历结点记录到一个栈里（直接用c++的vector实现即可），然后加以判断是否符合条件，递归完在出栈。
代码
class Solution {
public:
vector
<vector
<int>> pathSum(TreeNode
* root
, int sum
) {
vector
<vector
<int>> result
;
vector
<int> path
;
int path_value
= 0;
preorder(root
,path_value
,sum
,path
,result
);
return result
;
}
private:
void preorder(TreeNode
*node
,int &path_value
,int sum
,
vector
<int> &path
, vector
<vector
<int>> &result
){
if(!node
){
return;
}
path_value
+= node
->val
;
path
.push_back(node
->val
);
if(!node
->left
&& !node
->right
&& path_value
==sum
){
result
.push_back(path
);
}
preorder(node
->left
,path_value
,sum
,path
,result
);
preorder(node
->right
,path_value
,sum
,path
,result
);
path_value
-= node
->val
;
path
.pop_back();
}
};
LeetCode [236] 二叉树的最近公共祖先
问题描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
算法思路
先去找到以这两个节点为末尾的从根节点开始的两条路径，然后判断路经长短，两条路径同时向后遍历，找到长路径和短路径相同的最后面的那个节点，即为所求
算法代码
class Solution {
public:
TreeNode
* lowestCommonAncestor(TreeNode
* root
, TreeNode
* p
, TreeNode
* q
) {
vector
<TreeNode
*> path
;
vector
<TreeNode
*> node_p_path
;
vector
<TreeNode
*> node_q_path
;
int finish
= 0;
preorder(root
,p
,path
,node_p_path
,finish
);
path
.clear();
finish
=0;
preorder(root
,q
,path
,node_q_path
,finish
);
int path_len
=0;
if(node_p_path
.size() < node_q_path
.size()){
path_len
= node_p_path
.size();
}
else{
path_len
= node_q_path
.size();
}
TreeNode
*result
= 0;
for(int i
=0;i
<path_len
;i
++){
if(node_p_path
[i
] == node_q_path
[i
]){
result
= node_p_path
[i
];
}
}
return result
;
}
private:
void preorder(TreeNode
*node
,TreeNode
*search
,vector
<TreeNode
*> &path
,
vector
<TreeNode
*> &result
,int &finish
){
if(!node
|| finish
){
return;
}
path
.push_back(node
);
if(node
== search
){
finish
=1;
result
=path
;
}
preorder(node
->left
,search
,path
,result
,finish
);
preorder(node
->right
,search
,path
,result
,finish
);
path
.pop_back();
}
};
LeetCode [114] 二叉树展开为链表
问题描述
给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
算法思路
图片来自小象学院教程
算法代码
class Solution {
public:
void flatten(TreeNode
* root
) {
TreeNode
*last
= NULL;
preorder(root
,last
);
}
private:
void preorder(TreeNode
*node
,TreeNode
*&last
){
if(!node
){
return;
}
if(!node
->left
&& !node
->right
){
last
= node
;
return;
}
TreeNode
*left
= node
->left
;
TreeNode
*right
= node
->right
;
TreeNode
*left_last
= NULL;
TreeNode
*right_last
= NULL;
if(left
){
preorder(left
,left_last
);
node
->left
= NULL;
node
->right
= left
;
last
= left_last
;
}
if(right
){
preorder(right
,right_last
);
if(left_last
){
left_last
->right
= right
;
}
last
= right_last
;
}
}
};
LeetCode [199] 二叉树的右视图
题目描述
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例
输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
算法思想
运用层次遍历二叉树，记录每层最后一个结点
层次遍历大致算法：
设置队列Q
将根节点入队列Q
while(Q不为空){
去除队列头部结点node
对node访问
将node的左、右孩子入队列
}
算法代码
class Solution {
public:
vector
<int> rightSideView(TreeNode
* root
) {
vector
<int> view
;
queue
<pair
<TreeNode
*,int>> Q
;
if(root
){
Q
.push(make_pair(root
,0));
}
while(!Q
.empty()){
TreeNode
*node
= Q
.front().first
;
int depth
= Q
.front().second
;
Q
.pop();
if(view
.size()==depth
){
view
.push_back(node
->val
);
}
else{
view
[depth
] = node
->val
;
}
if(node
->left
){
Q
.push(make_pair(node
->left
,depth
+1));
}
if(node
->right
){
Q
.push(make_pair(node
->right
,depth
+1));
}
}
return view
;
}
};
LeetCode [207] 课程表
题目描述
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例
示例 1:
输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
深度遍历搜索
算法思路
用图操作写代码，用邻接表储存一个图，表示其依赖关系，用图的深度遍历方法。判断节点在深度搜索过程中有没有再度遇到同个节点（注意是在搜索过程中，而不是搜索完成回溯时）。如果再度遇见同一节点则该图有环，课程不能进行。
算法代码
struct GraphNode
{
int label
;
vector
<GraphNode
*> neighbors
;
GraphNode(int x
): label(x
) {};
};
class Solution {
public:
bool canFinish(int numCourses
, vector
<vector
<int>>& prerequisites
) {
vector
<GraphNode
*> graph
;
vector
<int> visit
;
for(int i
=0;i
<numCourses
;i
++){
graph
.push_back(new GraphNode(i
));
visit
.push_back(-1);
}
for(int i
=0;i
<prerequisites
.size();i
++){
GraphNode
*begin
= graph
[prerequisites
[i
][1]];
GraphNode
*end
= graph
[prerequisites
[i
][0]];
begin
->neighbors
.push_back(end
);
}
for(int i
=0;i
<graph
.size();i
++){
if(visit
[i
] == -1 && !DFS_graph(graph
[i
],visit
)){
return false;
}
}
for(int i
=0;i
<numCourses
;i
++){
delete graph
[i
];
}
return true;
}
private:
bool DFS_graph(GraphNode
*node
,vector
<int> &visit
){
visit
[node
->label
] = 0;
for(int i
=0;i
<node
->neighbors
.size();i
++){
if(visit
[node
->neighbors
[i
]->label
] == -1){
if(DFS_graph(node
->neighbors
[i
],visit
)==0){
return false;
}
}
else if(visit
[node
->neighbors
[i
]->label
]==0){
return false;
}
}
visit
[node
->label
] = 1;
return true;
}
};
拓扑排序（宽度优先搜索）
算法思路
创建一个队列，初始把入度为0的点加入队列，当队列不为空时执行： 弹出队头，让队头指向的那个节点的入度减一，且如果该节点入度为0则加入队列，进行循环。 直到队列为空时，如果依然有点的入度不为0，则该图有环！课程无法进行
算法代码
struct GraphNode
{
int label
;
vector
<GraphNode
*> neighbors
;
GraphNode(int x
): label(x
) {};
};
class Solution {
public:
bool canFinish(int numCourses
, vector
<vector
<int>>& prerequisites
) {
vector
<GraphNode
*> graph
;
vector
<int> degree
;
for(int i
=0;i
<numCourses
;i
++){
degree
.push_back(0);
graph
.push_back(new GraphNode(i
));
}
for(int i
=0;i
<prerequisites
.size();i
++){
GraphNode
*begin
= graph
[prerequisites
[i
][1]];
GraphNode
*end
= graph
[prerequisites
[i
][0]];
begin
->neighbors
.push_back(end
);
degree
[prerequisites
[i
][0]]++;
}
queue
<GraphNode
*> Q
;
for(int i
=0;i
<numCourses
;i
++){
if(degree
[i
]==0){
Q
.push(graph
[i
]);
}
}
while(!Q
.empty()){
GraphNode
*node
= Q
.front();
Q
.pop();
for(int i
=0;i
<node
->neighbors
.size();i
++){
degree
[node
->neighbors
[i
]->label
]--;
if(degree
[node
->neighbors
[i
]->label
]==0){
Q
.push(node
->neighbors
[i
]);
}
}
}
for(int i
=0;i
<graph
.size();i
++){
delete graph
[i
];
}
for(int i
=0;i
<graph
.size();i
++){
if(degree
[i
]){
return false;
}
}
return true;
}
};
ps: 小象学院教程 https://www.bilibili.com/video/BV1GW411Q77S?t=7029&p=2
