数据结构第五章-二叉树与图
预备知识：二叉树基础知识
二叉树类似于一个有两个指针的链表
二叉树的深度搜索
前序遍历：先访问他本身，然后访问左子树和右子树 中序遍历：先遍历左子树，访问他本身，然后遍历右子树 后序遍历：先访问左子树，在访问右子树，再访问本身
路径之和
#medium 思路不是很难想 113. 路径总和 II - 力扣（LeetCode） 给定一个二叉树和整数sum，找出所有从根节点到叶节点的路径，这些路径上的节点累加和为sum
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
这里是后序遍历不是后续遍历
解决方法如下
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
std::vector<std::vector<int> > result;
std:: vector<int> path;//路径栈
int path_value = 0;//路径累加和
preorder(root,path_value,targetSum,path,result);
return result;
}
private :
void preorder(TreeNode* node,int &path_value,int targetSum,std::vector<int>&path,std::vector<std::vector<int> > &result){
if(!node){//如果节点空了
return ;
}
path_value = path_value + node->val; //前序要做的
path.push_back(node->val);
if(!node->left&&!node->right&&path_value == targetSum){
result.push_back(path);
}
preorder(node->left,path_value,targetSum,path,result);//遍历左树
preorder(node->right,path_value,targetSum,path,result);//遍历右树
path_value = path_value - node->val;//后序要做的
path.pop_back();
}
};
在递归中当函数第一次执行到函数尾部的时候意味着函数执行到了叶节点上
最近的公共祖先(LCA)
#medium 236. 二叉树的最近公共祖先 - 力扣（LeetCode）
最近公共祖先： 两节点v和w的最近公共祖先u，满足在树上最低（离根最远） ，且v,w都是u的子孙
思路
与上一题方法类似
从根节点到某一结点的路径搜索
void preorder(TreeNode* node,//正在遍历的节点
TreeNode* search,//待搜索节点
std::vector<TreeNode*>&path,//遍历时的节点路径
std::vector<TreeNode*>&result,//最终结果
int &finish){//记录是否找到节点search的变量，未找到的时是0，找到是1
if(!node||finish){//node为空或者已经找search节点直接返回，结束搜索
return ;
}
path.push_back(node);//先序遍历把节点压入栈
if(node == search){
finish = 1;
result = path;//当前path存储到result里面
}
preorder(node->left,search,path,result,finish);
preorder(node->right,search,path,result,finish);
path.pop_back();//结束遍历node,把node节点弹出path栈
}
^573c39
解决方法如下
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
std::vector<TreeNode*> path;
std::vector<TreeNode*> node_p_path;//存储p节点路径
std::vector<TreeNode*>node_q_path; //存储q节点路径
int finish = 0;//记录是否完成搜索的finish
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++){ //同时便利p,q两个节点上路径上的节点
if(node_q_path[i] == node_p_path[i]){
result = node_p_path[i]; //找到了公共祖先
}
}
return result;
}
[[第五章：二叉树与图#^573c39|preorder函数]]
二叉树转链表
不考虑就地转换时候（方法一）
#medium
必须要就地转换的时候（方法二）
#hard
114. 二叉树展开为链表 - 力扣（LeetCode）
给定一个二叉树，**就地转换（ 不申请额外节点空间 ）**为单链表，单链表中节点顺序为二叉树前序遍历顺序
单链表仍然使用树的数据结构，即left = NULL;rignt = next
方法一
如上图所示，但是不符合就地转换
这个代码把树里面的所有节点储存到node_vec里面，申请了额外的空间
解决方法如下
class Solution {
public:
void flatten(TreeNode* root) {
std::vector<TreeNode*>node_vec;
preorder(root,node_vec);
for(int i = 1;i< node_vec.size();i++){
node_vec[i-1]->left = NULL;
node_vec[i-1]->right = node_vec[i];
}
}
private :
void preorder(TreeNode* node,std::vector<TreeNode*>&node_vec){
if(!node){
return;
}
node_vec.push_back(node);
preorder(node->left,node_vec);
preorder(node->right,node_vec);
}
};
方法二
递归的过程中进行处理
中序的时候左子树已经被拉直了，此时需要做什么
把左子树的最后一个节点和右子树的第一个节点相连 所以需要把子树的最后一个节点传出
前序需要做什么
到达叶节点的时候return掉 对左子树和右子树的last指针进行备份 传出的last节点需要再前序过程中定义
内部过程详解
解决方法如下
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;//将该节点的last 保存为左子树的last
}
if(right){//若有右子树，递归将右子树转换为单链表
preorder(right,right_last);
if(left_last){//若是node找到左子树最后一个节点（有左子树）
left_last -> right = right;
}
last = right_last;
}
}
};
为什么right_last和left_last能够放在子树的最后一个节点上？
left_last变量在preorder函数中的作用是记录当前子树的最后一个节点。当递归到叶子节点时，left_last会被更新为当前节点。因此，当递归到树的最左边的叶子节点时，left_last不再为空。 举个例子，假设我们有一棵树，它的根节点为node，它的左子树为left。当我们调用preorder(node, last)时，函数会检查node是否有左子树。如果有，那么函数会递归调用preorder(left, left_last)。在这次递归调用中，函数会继续检查left是否有左子树。这个过程会一直持续下去，直到递归到最左边的叶子节点。在这个叶子节点处，left_last会被更新为当前节点。因此，在这之后，left_last不再为空。 由于node是值传递，而last是引用传递，这意味着每一层递归里面node都是独立的，而last会随着递归的进程而更新,在例子里面，node_left会一直初始化，直到遍历到3，(此时记录left_last为3）然后进行对于2的右子树的遍历，直到将左子树全部遍历为链表，然后对右子树进行遍历 在这段代码中，last是preorder函数的一个参数，它是一个指向TreeNode类型的指针的引用。在对左子树进行递归调用时，我们将left_last作为参数传递给了下一层递归。在下一层递归中，last参数就指向了left_last变量。因此，在下一层递归中，当我们更新last的值时，实际上就是在更新left_last的值。 同理，在对右子树进行递归调用时，我们将right_last作为参数传递给了下一层递归。在下一层递归中，last参数就指向了right_last变量。因此，在下一层递归中，当我们更新last的值时，实际上就是在更新right_last的值。
再看不懂我也没办法了
二叉树层次遍历（宽度优先搜索）
按照树的层次依次来访问节点，层次遍历使用队列对遍历节点进行存储，先进入队列的节点没有先遍历左节点和右节点
红色为已访问完成，蓝色为正在队列里面等待访问
从侧面观察二叉树
#medium 199. 二叉树的右视图 - 力扣（LeetCode） 给定一个二叉树，假设从二叉树的右侧观察它，将观察到的节点从上到下的顺序进行输出 示例：
输入: [1,2,3,null,5,null,4]
输出:[1,3,4]
输入: [1,null,3]
输出:[1,3]
怎样记录每一层出现的最后一个节点
解决方法如下
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
std::vector<int> view;//按层遍历的最后一个节点
std::queue<std::pair<TreeNode* ,int> >Q;//宽度有限搜索队列
if(root){
Q.push(std::make_pair(root,0));//节点非空的时候把<root,0>进入队列
}
while(!Q.empty()){
TreeNode* node = Q.front().first;//搜索节点
int depth = Q.front().second;//搜索节点层数
Q.pop();
if(view.size() == depth){//当view的大小与深度相等，说明这是该层的第一个元素，所以把这个值push进入view
view.push_back(node->val);
}
else{//如果不相等只需要修改这一层的值，由于广度搜索从左往右，最后自然会到该层最后一个元素
view[depth] = node->val;
}
if(node->left){//push进左右节点，深度加1
Q.push(std::make_pair(node->left,depth+1));
}
if(node->right){
Q.push(std::make_pair(node->right,depth+1));
}
}
return view;
}
};
图的定义和基础知识
图的两种表示方法
行代表具体哪个顶点，列代表顶点和顶点之间的逻辑关系
为1的时候是前面的维度指向后面的维度
时间复杂度很大
用指针数组，把与该顶点的相连的顶点push到数组里面
其中 邻接表的连接方法可以理解为
begin->neighbors.push_back(end) 起始的节点有一个vector.size()个他指向的节点
图的遍历
二叉树没有环路，图有，所以需要一个数组来表示节点是否被查找到
代码如下：
#include <stdio.h>
#include <vector>
struct GraphNode{
int label;//图顶点的值
std::vector<GraphNode *> neighbors;//相邻节点的值
GraphNode(int x) : label(x) {};
};
/*这种DFS方法也可以用来表示树或者森林*/
void DFS_graph(GraphNode *node, int visit[]){
visit[node->label] = 1;//标记已经访问的顶点
printf("%d ", node->label);
for (int i = 0; i < node->neighbors.size(); i++){//访问相连且不为没访问过的顶点
if (visit[node->neighbors[i]->label] == 0){
DFS_graph(node->neighbors[i], visit);
}
}
}
int main(){
const int MAX_N = 5;//创建图的顶点
GraphNode *Graph[MAX_N];
for (int i = 0; i < MAX_N; i++){
Graph[i] = new GraphNode(i);
}
//添加图的边，注意添加边的顺序
Graph[0]->neighbors.push_back(Graph[4]);
Graph[0]->neighbors.push_back(Graph[2]);
Graph[1]->neighbors.push_back(Graph[0]);
Graph[1]->neighbors.push_back(Graph[2]);
Graph[2]->neighbors.push_back(Graph[3]);
Graph[3]->neighbors.push_back(Graph[4]);
Graph[4]->neighbors.push_back(Graph[3]);
int visit[MAX_N] = {0};//标记已经访问的顶点
for (int i = 0; i < MAX_N; i++){
if (visit[i] == 0){//顶点没有标记才会访问
printf("From label(%d) : ", Graph[i]->label);
DFS_graph(Graph[i], visit);
printf("\n");
}
}
for (int i = 0; i < MAX_N; i++){
delete Graph[i];
}
return 0;
}
代码如下
#include <stdio.h>
#include <vector>
#include <queue>
struct GraphNode{
int label;
std::vector<GraphNode *> neighbors;
GraphNode(int x) : label(x) {};
};
void BFS_graph(GraphNode *node, int visit[]){
std::queue<GraphNode *> Q;//宽度优先使用队列
Q.push(node);
visit[node->label] = 1;
while(!Q.empty()){//Q不为空一直循环
GraphNode *node = Q.front();
Q.pop();
printf("%d ", node->label);
for (int i = 0; i < node->neighbors.size(); i++){
if (visit[node->neighbors[i]->label] == 0){//没遍历过时才遍历
Q.push(node->neighbors[i]);
visit[node->neighbors[i]->label] = 1;
}
}
}
}
int main(){
const int MAX_N = 5;//创建顶点
GraphNode *Graph[MAX_N];
for (int i = 0; i < MAX_N; i++){
Graph[i] = new GraphNode(i);
}
//添加边
Graph[0]->neighbors.push_back(Graph[4]);
Graph[0]->neighbors.push_back(Graph[2]);
Graph[1]->neighbors.push_back(Graph[0]);
Graph[1]->neighbors.push_back(Graph[2]);
Graph[2]->neighbors.push_back(Graph[3]);
Graph[3]->neighbors.push_back(Graph[4]);
Graph[4]->neighbors.push_back(Graph[3]);
int visit[MAX_N] = {0};//标记已经访问到的顶点
for (int i = 0; i < MAX_N; i++){
if (visit[i] == 0){
printf("From label(%d) : ", Graph[i]->label);
BFS_graph(Graph[i], visit);
printf("\n");
}
}
for (int i = 0; i < MAX_N; i++){
delete Graph[i];
}
return 0;
}
课程安排
#medium 207. 课程表 - 力扣（LeetCode） n个课程，课程之间有依赖关系，如果完成A需要先完成B，已知所有课程的依赖关系，求是否可以完成n个课程
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。1对0依赖。
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的，1对0依赖，0对1依赖。
方法1 深度优先搜索
注意：是正在搜索而不是搜索完成，是深度搜索搜索到原点而不是回退到远点
无环情况：
有环情况下：
解决方法如下
/*DFS代码*/
struct GraphNode{
int label;
std::vector<GraphNode *> neighbors;
GraphNode(int x) : label(x) {};
};//节点访问状态，-1没有访问，0正在访问，1为访问完成
bool DFS_graph(GraphNode *node, std::vector<int> &visit){
visit[node->label] = 0;//前序时候正在访问，标记为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){//深搜时发现有环返回false
return false;
}
}
else if (visit[node->neighbors[i]->label] == 0){//当node本身的相邻节点出现0的时候说明有环
return false;
}
}
visit[node->label] = 1;//后序时访问完成，标记为1
return true;
}
/*调用代码*/
class Solution {
public:
bool canFinish(int numCourses,
std::vector<std::vector<int> >& prerequisites) {
std::vector<GraphNode*> graph; //邻接表
std::vector<int> visit;//节点访问状态，-1表示没有访问过，0表示正在访问，1代表访问完成
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);//课程2指向课程1
}
for (int i = 0; i < graph.size(); i++){
if (visit[i] == -1 && !DFS_graph(graph[i], visit)){//如果节点没有访问过则执行DFS,如果DFS遇到环，返回无法完成
return false;
}
}
for (int i = 0; i < numCourses; i++){
delete graph[i];
}
return true;//返回可以完成
}
};
方法2 拓扑排序（宽度优先搜索）（kahn算法）
入度
该课程依赖于几门课程，入度就是几，比如1依赖于2和0，那么入度就是2 官方解释 ：
入度（In-degree）是指有向图中，指向某个节点的边的数量。
无环情况
解决方法如下
struct GraphNode{
int label;
std::vector<GraphNode *> neighbors;
GraphNode(int x) : label(x) {};
};
class Solution {
public:
bool canFinish(int numCourses,
std::vector<std::vector<int> >& prerequisites) {
std::vector<GraphNode*> graph;//入度数组
std::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]]++; //课程1的入度增加
}
/*拓扑排序算法*/
std::queue<GraphNode *> Q;//BFS队列
for (int i = 0; i < numCourses; i++){
if (degree[i] == 0){//如果入度为0，则push进入队列
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){//如果此时入度为0，则将此节点push进队列
Q.push(node->neighbors[i]);
}
}
}
for (int i = 0; i < graph.size(); i++){
delete graph[i];
}
for (int i = 0; i < degree.size(); i++){
if (degree[i]){//再入度数组里面存在一个值不为0
return false;
}
}
return true;
}
};
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 name1110
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果