【C++笔记】C++常见二叉树OJ和拓扑排序

【C++笔记】C++常见二叉树OJ和拓扑排序

🔥个人主页：大白的编程日记

🔥专栏：C++笔记

---

前言

哈喽，各位小伙伴大家好!上期我们讲了C++的类型转换。今天我们来讲一下C++常见二叉树OJ和拓扑排序。话不多说，我们进入正题！向大厂冲锋

一.二叉树OJ

1.1 根据二叉树创建字符串

• 题目：根据二叉树创建字符串
  
• 思路分析

• 代码实现

class Solution {
public:string tree2str(TreeNode* root) {string ret;if(root==nullptr){return "";}ret+=to_string(root->val);//左不为空进入//左为空 右不为空进入不省略空号if(root->right||root->left){ret+='(';ret+=tree2str(root->left);ret+=')';}//右为空则不进入省略if(root->right){ret+='(';ret+=tree2str(root->right);ret+=')';}return ret;}
};

1.2 二叉树的层序遍历

• 题目：二叉树的层序遍历
  

• 思路分析

• 代码实现

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ret;if(root==nullptr){return {};}queue<TreeNode*> q;q.push(root);int size=1;while(q.size()){vector<int> v;while(size--){TreeNode* t=q.front();v.push_back(t->val);q.pop();if(t->left){q.push(t->left);}if(t->right){q.push(t->right);}}ret.push_back(v);size=q.size();}return ret;}
};

1.3 二叉树的最近公共祖先

• 题目：二叉树的最近公共祖先
  

• 思路分析：

• 代码实现
  方法一：

class Solution {
public:bool find(TreeNode* root,TreeNode* x){if(root==nullptr){return false;}return root==x||find(root->left,x)||find(root->right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==nullptr){return nullptr;}if(root==p||root==q){return root;}bool pinleft=find(root->left,p);bool pinright=!pinleft;bool qinleft=find(root->left,q);bool qinright=!qinleft;if((pinleft&&qinright)||(pinright&&qinleft)){return root;}else if(pinleft&&qinleft){return lowestCommonAncestor(root->left,p,q);}else{return lowestCommonAncestor(root->right,p,q);}}
};

方法二：

class Solution {
public:bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& st){if(root==nullptr){return false;}st.push(root);if(root==x){return true;}if(GetPath(root->left,x,st)){return true;}if(GetPath(root->right,x,st)){return true;}st.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> stl,str;GetPath(root,p,stl);GetPath(root,q,str);while(stl.size()!=str.size()){if(stl.size()>str.size()){stl.pop();}else{str.pop();}}while(stl.top()!=str.top()){stl.pop();str.pop();}return str.top();}
};

1.4 将二叉搜索树转化为排序的双向链表

• 题目：将二叉搜索树转化为排序的双向链表
  
• 思路分析

• 代码实现
  方法一

class Solution {
public:Node* treeToDoublyList(Node* root) {if(root==nullptr){return root;}vector<Node*> v;auto dfs=[&](this auto&& dfs,Node* root)->void{if(root==nullptr){return ;}dfs(root->left);v.push_back(root);dfs(root->right);};dfs(root);for(int i=0;i<v.size()-1;i++){v[i]->right=v[i+1];v[i+1]->left=v[i];}v[0]->left=v[v.size()-1];v[v.size()-1]->right=v[0];return v[0];}
};

方法二

class Solution {
public:void InOrderCovert(Node*cur,Node*& prev)//中序遍历同时修改指针prev为中序前一个cur当前中序{if(cur==nullptr){return;}InOrderCovert(cur->left,prev);cur->left=prev;if(prev){prev->right=cur;}//修改前后指针prev=cur;//更新prevInOrderCovert(cur->right,prev);}Node* treeToDoublyList(Node* root) {if(root==nullptr){return root;}Node* prev=nullptr;InOrderCovert(root,prev);Node* head=root;while(head->left){head=head->left;}head->left=prev;prev->right=head;//首尾相连return head;}
};

• 下面的这三道题都是我看灵神的题解 发现讲的特别好 思路也很清晰 通俗易通。 直接上按照灵神的思路图了。

1.5 从前序与中序遍历序列构造二叉树

• 题目：从前序与中序遍历序列构造二叉树

• 思路分析
  

• 代码实现

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if (preorder.empty()) { // 空节点return nullptr;}int rootValue = preorder[0];int left_size = 0;// 使用for循环查找根节点在中序遍历中的位置for (int i = 0; i < inorder.size(); ++i) {if (inorder[i] == rootValue) {left_size = i; // 找到根节点的位置，即左子树的大小break;}}vector<int> pre1(preorder.begin() + 1, preorder.begin() + 1 + left_size);vector<int> pre2(preorder.begin() + 1 + left_size, preorder.end());vector<int> in1(inorder.begin(), inorder.begin() + left_size);vector<int> in2(inorder.begin() + left_size + 1, inorder.end());TreeNode* left = buildTree(pre1, in1);TreeNode* right = buildTree(pre2, in2);return new TreeNode(preorder[0], left, right);}
};

1.6 从中序与后序遍历序列构造二叉树

• 题目：从中序与后序遍历序列构造二叉树
  
• 思路分析
  
• 代码实现

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n = inorder.size();unordered_map<int, int> index;for (int i = 0; i < n; i++) {index[inorder[i]] = i;}function<TreeNode*(int, int, int, int)> dfs = [&](int in_l, int in_r, int post_l, int post_r) -> TreeNode* {if (post_l > post_r) { // 空节点，注意左闭右闭区间的判断条件return nullptr;}int rootValue = postorder[post_r];int rootIndex = index[rootValue];int left_size = rootIndex - in_l; // 左子树的大小TreeNode* root = new TreeNode(rootValue);root->left = dfs(in_l, rootIndex - 1, post_l, post_l + left_size - 1);root->right = dfs(rootIndex + 1, in_r, post_l + left_size, post_r - 1);return root;};return dfs(0, n - 1, 0, n - 1); // 左闭右闭区间}
};

1.7 根据前序和后续遍历构建二叉树

• 题目：根据前序和后续遍历构建二叉树
  

• 思路分析

• 首先说明，如果只知道前序遍历和后序遍历，这棵二叉树不一定是唯一的，如下图。
  

• 注：如果二叉树的每个非叶节点都有两个儿子，知道前序和后序就能唯一确定这棵二叉树。

• 题目说，如果存在多个答案，我们可以返回其中任何一个。那么不妨规定：无论什么情况，在前序遍历中，preorder[1] 都是左子树的根节点值。

• 代码实现

class Solution {
public:TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {int n = preorder.size();vector<int> index(n + 1); // 用于快速查找 postorder 中元素的索引for (int i = 0; i < n; i++) {index[postorder[i]] = i;}// 使用左闭右闭区间 [pre_l, pre_r] 和 [post_l, post_r]auto dfs = [&](this auto&& dfs, int pre_l, int pre_r, int post_l, int post_r) -> TreeNode* {if (pre_l > pre_r) { // 空节点return nullptr;}if (pre_l == pre_r) { // 叶子节点return new TreeNode(preorder[pre_l]);}int left_size = index[preorder[pre_l + 1]] - post_l + 1; // 左子树的大小TreeNode* left = dfs(pre_l + 1, pre_l + left_size, post_l, post_l + left_size - 1);TreeNode* right = dfs(pre_l + left_size + 1, pre_r, post_l + left_size, post_r - 1);return new TreeNode(preorder[pre_l], left, right);};return dfs(0, n - 1, 0, n - 1); // 左闭右闭区间}
};

1.8 二叉树前序遍历的非递归

• 题目：二叉树的前序遍历

• 思路分析
  

• 代码实现

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur=root;//把遍历分为遍历左子树和右子树while(cur||!st.empty())//当前右子树不为空或还有右子树待访问{while(cur)//访问根 左子树{v.push_back(cur->val);//访问根st.push(cur);cur=cur->left;}TreeNode* tmp=st.top();st.pop();//弹出避免二次递归并且更新上上级递归cur=tmp->right;//转为子问题访问右子树}return v;}
};

1.9 二叉树中序遍历的非递归

• 题目：二叉树的中序遍历

• 思路分析
  

• 代码实现

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root;while (cur || !st.empty())//右子树不为空或者当前子树还有根和根子树没有访问{while (cur)//访问左子树{st.push(cur);cur = cur->left;}TreeNode* tmp = st.top();st.pop();//弹出避免二次递归并且更新上上级递归v.push_back(tmp->val);//访问根cur = tmp->right;//转为子问题访问右子树}return v;}
};

1.10 二叉树的后序遍历

• 题目：二叉树的后序遍历

• 思路分析
  

• 代码实现

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root;while (cur || !st.empty())//左子树不为空或者还有根和右子树没有访问{while (cur)//访问根 右子树{st.push(cur);v.push_back(cur->val);//访问根cur = cur->right;//访问右子树}TreeNode* root = st.top();st.pop();//弹出避免二次递归并且更新上上级递归cur = root->left;//转为子问题访问左子树}reverse(v.begin(),v.end());//逆置return v;}
};

二. 拓扑排序

拓扑排序是一种对有向无环图（DAG，Directed Acyclic Graph）的顶点进行线性排序的方法，使得对于图中的每一个边 (u,v)，顶点 u 在排序中都出现在顶点 v 的前面。拓扑排序在实际应用中非常重要，例如在任务调度、项目管理、编译原理等领域。

2.1 动画演示

2.2 课程表

• 题目：课程表
• 思路分析
  同上 判断是否有环
• 代码实现

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> in(numCourses);unordered_map<int,vector<int>> hash;for(auto& x:prerequisites)//维护每个节点的入度{int a=x[0],b=x[1];hash[b].push_back(a);in[a]++;}queue<int> q;for(int i=0;i<numCourses;i++)//维护每个节点的边信息{if(in[i]==0){q.push(i);}}while(q.size())//bfs{int i=q.front();q.pop();for(auto& x:hash[i]){in[x]--;if(in[x]==0){q.push(x);}}}for(auto& x:in)//判断是否有环{if(x){return false;}}return true;}
};

2.3 课程表2

• 题目：
• 思路分析
  同上 拓扑排序
• 代码实现

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> in(numCourses),ret;unordered_map<int,vector<int>> hash;for(auto& x:prerequisites){int a=x[0],b=x[1];hash[b].push_back(a);in[a]++;}queue<int> q;for(int i=0;i<numCourses;i++){if(in[i]==0){q.push(i);ret.push_back(i);}}while(q.size()){int i=q.front();q.pop();for(auto& x:hash[i]){in[x]--;if(in[x]==0){q.push(x);ret.push_back(x);}}}for(auto& x:in){if(x){return {};}}return ret;}
};

2.4 火星词典

• 题目：火星词典

• 思路分析
  

• 代码实现

class Solution {
public:string alienOrder(vector<string>& words) {string ret;int n=words.size();unordered_map<char,unordered_set<char>> edge;//出度信息unordered_map<char,int> in;//入度信息for(auto& s:words){for(auto ch:s){in[ch]=0;}}for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){int len1=words[i].size();int len2=words[j].size();int l=0,r=0;while(l<len1&&r<len2){while(l<len1&&r<len2&&words[i][l]==words[j][r])//找到不相等的位置{l++;r++;}char a=words[i][l],b=words[j][r];if(l<len1&&r<len2&&(!edge.count(a)||!edge[a].count(b)))//防止重复信息{edge[a].insert(b);in[b]++;}if(r==len2&&l<len1)//处理边界情况{return "";}break;}}}queue<char> q;for(auto [a,b]:in)//入度为0的入队列{if(b==0){q.push(a);}}while(q.size()){char t=q.front();ret+=t;q.pop();for(auto x:edge[t]){if(--in[x]==0)//出度--判断是否入度为0{q.push(x);}}}for(auto [a,b]:in){if(b!=0){return "";//判断是否有向无环图}}return ret;}
};

后言

这就是C++常见二叉树OJ和拓扑排序。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~