二叉树与图（C++刷题笔记）

113. 路径总和 II

力扣

• 从根节点深度遍历二叉树，先序遍历时，将节点存储至path栈中，使用path_val累加节点值

• 当遍历到叶子节点，检查path_val是否为sum，若是，则将pathpush进入res的结果中去

• 在后续变量，将该节点从path栈中弹出，path_val减去节点值

题目代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/class Solution {
public:vector<vector<int>> pathSum(TreeNode* root, int targetSum) {vector<vector<int> >res;vector<int>path;int path_val=0;preorder(root,path_val,targetSum,path,res);return res;}void preorder(TreeNode *nd,int &path_val,int sum,vector<int>&path,vector<vector<int> >&res){if(!nd)return;path_val+=nd->val;path.push_back(nd->val);if(!nd->right&&!nd->left&&path_val==sum){res.push_back(path);}preorder(nd->left,path_val,sum,path,res);preorder(nd->right,path_val,sum,path,res);path_val-=nd->val;path.pop_back();}};

236. 二叉树的最近公共祖先

力扣

• 两个节点公共祖先一定从根节点，至这两个节点的路径上

• 由于求公共祖先中的最近公共祖先，那么即同时出现在这两条路径上的里根几点最远的节点

• 求两个节点路径最后一个相同的节点

求根节点到某一个节点的路径

• 从根节点遍历至该节点，找到节点后就结束搜索

• 将遍历过程中遇到的节点按顺序存储，节点即路径

  void dfs(TreeNode *nd,TreeNode *search,vector<TreeNode *>&path,vector<TreeNode *>&res,int &end){if(!nd||end==1)return;path.push_back(nd);if(nd==search){end=1;res=path;}dfs(nd->left,search,path,res,end);dfs(nd->right,search,path,res,end);path.pop_back();}

求两路径下最后一个相同节点

• 求出较短路径长度n

• 同时遍历p节点与q节点路径，遍历n个节点，最后一个相同的节点即最近公共祖先

题目代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {vector<TreeNode *>path;vector<TreeNode *>p_path;vector<TreeNode *>q_path;int end=0;dfs(root,p,path,p_path,end);path.clear();end=0;dfs(root,q,path,q_path,end);int path_len=0;if(p_path.size()<q_path.size()){path_len=p_path.size();} else{path_len=q_path.size();}TreeNode *res=NULL;for (int i = 0; i < path_len; ++i) {if(p_path[i]==q_path[i]){res=p_path[i];}}return res;}void dfs(TreeNode *nd,TreeNode *search,vector<TreeNode *>&path,vector<TreeNode *>&res,int &end){if(!nd||end==1)return;path.push_back(nd);if(nd==search){end=1;res=path;}dfs(nd->left,search,path,res,end);dfs(nd->right,search,path,res,end);path.pop_back();}
};

114. 二叉树展开为链表

力扣

• 前序遍历二叉树，将指针push进入vector，顺序遍历vector中节点，链接相邻两节点

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void flatten(TreeNode* root) {vector<TreeNode *>vec;preorder(root,vec);for (int i = 1; i <vec.size(); ++i) {vec[i-1]->left=NULL;vec[i-1]->right=vec[i];}}void preorder(TreeNode *nd,vector<TreeNode *>&vec){if(!nd)return;vec.push_back(nd);preorder(nd->left,vec);preorder(nd->right,vec);}
};

199. 二叉树的右视图

• 从二叉树的右侧观察它，将观察到的节点从上到下顺序输出，就是求层次遍历二叉树，每层中最后一个节点

• 层序遍历时，将节点与层数绑定为pair，压入队列时，将节点与层数同时压入队列，并记录每一层出现的最后一个节点

• 层序遍历中，每一层的最后一个节点最后遍历到，随时更新对每层的最后一个节点即可

题目代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
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 *nd=Q.front().first;int layer=Q.front().second;Q.pop();if(view.size()==layer){view.push_back(nd->val);} else{view[layer]=nd->val;}if(nd->left){Q.push(make_pair(nd->left,layer+1));}if(nd->right){Q.push(make_pair(nd->right,layer+1));}}return view;}
};

207. 课程表

力扣

• n个课程m个依赖关系，看成顶点个数为n，边个数为m的有向图

• 若为有向无环图，则可以完成课程

• 否则不能

判断图是否有环

• 深度优先遍历，如果正在遍历某一顶点（还未退出该顶点），又回到了该顶点，证明图有环

题目代码

struct node{int label;vector<node *>neighbors;//邻接表node(int x):label(x){};
};
class Solution {
public://0 正在访问 -1没有访问 1访问过bool dfs(node *nd,vector<int>&vis){vis[nd->label]=0;for (int i = 0; i <nd->neighbors.size() ; ++i) {if(vis[nd->neighbors[i]->label]==-1){if(dfs(nd->neighbors[i],vis)==0){return false;}}else if(vis[nd->neighbors[i]->label]==0){return false;}}vis[nd->label]=1;return true;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<node*>graph;vector<int>vis;for (int i = 0; i < numCourses; ++i){graph.push_back(new node(i));vis.push_back(-1);}for (int i = 0; i < prerequisites.size(); ++i){node *begin=graph[prerequisites[i][1]];node *end=graph[prerequisites[i][0]];begin->neighbors.push_back(end);}for (int i = 0; i < graph.size(); ++i){if(vis[i]==-1&&!dfs(graph[i],vis)){return false;}}return true;}
};

拓扑排序

宽度优先搜索，将入度为0的点添加至队列，完成一个顶点的搜索时，把它指向的所有顶点的入度都减一，若此时莫顶点入读为0则添加队列，完成宽度优先搜索后，所有点入度为0，则图无环，否则有环

题目代码

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {vector<int> in;vector<vector<int> > graph;for (int i = 0; i < numCourses; ++i) {graph.push_back(vector<int>());in.push_back(0);}for (int i = 0; i < prerequisites.size(); ++i) {int end = prerequisites[i][0];int start = prerequisites[i][1];graph[start].push_back(end);in[end]++;}queue<int> Q;for (int i = 0; i < in.size(); ++i) {if (in[i] == 0) {Q.push(i);}}while (!Q.empty()) {int node = Q.front();Q.pop();for (int i = 0; i < graph[node].size(); ++i) {in[graph[node][i]]--;if (in[graph[node][i]] == 0) {Q.push(graph[node][i]);}}}for (int i = 0; i < in.size(); ++i) {if (in[i]) {return false;}}return true;}
};