一遍过，本题运用的kruskal的思想，通过并查集实现。获得两个点以及两个点间的距离，然后从集合中找出距离的最小值。加入到图的集合中，当把所有边都遍历完后，由于这个题，图肯定是连通的。所以只要记录加进来的边的长度(也就是两点间的距离就行）。 #include<iostream> #include<map> #include<vector> #include<algorithm> #include<math.h> using namespace std; int n; const int maxn=101; float res; str...

几个题基本都是Kruskal算法 #include<iostream> #include<vector> #include<map> #include<algorithm> using namespace std; const int maxn=200; int sum; struct home{ int x,y; int height; int state; inline bool operator < (const home &a)const{ return height<a.height; } }; vector<...

这个题也太🐕了0 0空集是树(没好好读题)有环不是树(没想到)其他并查集判断是否是一个连通图，如果是的话且没环就是树 #include<iostream> #include<map> #include<vector> using namespace std; const int maxn=10001; int father[maxn]; int height[maxn]; int indegree[maxn]; bool flag=false; map<int,int> mp;//记录点有没有出现过 int index=0; void init...

使用并查集和dfs都可以解决这个问题。如下是并查集解决的过程。相对于普通问题，主要是Union函数发生了变化 #include<iostream> #include<map> #include<string> using namespace std; //头是要点权最高的来。 //边权怎么记录? const int maxn=1001; int father[maxn]; int height[maxn]; //点权 int weight[maxn]; //规定顺序假如输入的是 AAA BBB 10，那么A的边权+10，B的边权不加。这样防止重复加边权，而且...

并查集的板子，一开始不会做，后来多做了几道就差不多会了。普通并查集只是顺序的节点号。但是本题给出的节点号不是顺序的，所以这里没有采用数组的方式，而是采用了map散列表的方式。当然通过dfs也可以很好的解决这个题目。通过对所有节点进行dfs。只要没有全遍历到，那就sum++； #include<iostream> #include<vector> #include<map> #include<algorithm> using namespace std; map<int,int> father; //通过散列表map实现的father数...

https://www.jianshu.com/p/5ad3e97d54a3

使用priority_queue，并且重载运算符就可以。但是要注意优先队列是大根堆。和sort是相反的。 #include<iostream> #include<math.h> #include<queue> using namespace std; struct complex { int a;int b; inline bool operator < (const complex &c)const{ if((a*a+b*b)==(c.a*c.a+c.b*c.b)){ return c.b>b; }return (a*a+b*b)&lt...

先建树，通过insert()插入节点。二叉搜索树的递归建立的过程如下:插入代码： TreeNode *BuildTree(TreeNode *root,int x){ if(root==NULL) root=new TreeNode(x); else if(root->val<x) root->right=BuildTree(root->right,x); else if(root->val>x) root->left=BuildTree(root->left,x); return root; }然后判断两树是否相等？可以遍历前序，如果不相等则不...

构造二叉树可以通过 前序+中序 、后序+中序两种方法。 这两种方法的核心思路都是 通过前/后序确定二叉树的根节点，然后在中序中根据根节点进行划分。然后递归。   前序+中序     class Solution { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { return BuildTree(0,pre.size()-1,0,vin.size()-1,pre,vin); } TreeNode* BuildTree(int leftpre,int rightpre,i...

xuexi!

做二叉树已经有两天的时间了，这两天在牛客上把剑指offer中和牛客考/保研机试中的树的题都做了。emmm，感受颇深。下面开始正题。 树的本质就是递归！递归！递归！   目录 一、树的结构，给出leetcode常用的标准板子； 二、遍历方法 1.前序遍历 2.中序遍历 3.后序遍历 4.层次遍历 三、相关题目（以剑指offer为准） 1.二叉树的镜像 2.树的子结构 3.从上往下打印二叉树 3.1 相似题目1 3.2 相似题目2 （按之字形顺序打印二叉树） 4.二叉搜索树的后序遍历序列 5.二叉树中和为某一值的路径  一、树的结构，给出leetcode常用的标准板子；   struct Tree...

二叉平衡树中序遍历是有序的。只需要中序遍历就好了 class Solution { public: int index; TreeNode* root=NULL; TreeNode* KthNode(TreeNode* pRoot, int k) { //中序遍历，第k个 index=k; inOrder(pRoot); return root; } void inOrder(TreeNode *pRoot) { if(pRoot==NULL) return ; inOrder(pRoot->left); index--; if(index==0){ root=pRoot; return...