P1030 [NOIP2001 普及组] 求先序排列

思路

后序遍历的最后一个字符即为根节点，在中序序列中找到该字符即可将该数分为左右子树。递归做下去直到为空即可。
已知前序遍历和中序遍历求后序遍历也是同样的思路。

实现

#include<bits/stdc++.h>
using namespace std;
int n;
string s1,s2;
void f(string in,string hou)
{
	if(hou.empty()) return;
	char root = hou[hou.size()-1];
	putchar(root);
	int pos = in.find(root);
	hou.erase(hou.end()-1);
	string lefthou = hou.substr(0,pos);
	string righthou = hou.substr(pos);
	string leftin = in.substr(0,pos);
	string rightin = in.substr(pos+1);
	f(leftin,lefthou);
	f(rightin,righthou);
}
int main()
{
	cin>>s1>>s2;
	f(s1,s2);
}

P4715 【深基16.例1】淘汰赛

思路

写了一个队列，没有明白这个题和二叉树特别明显的关系是…?

实现

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
	cin>>n;
	n = pow(2,n);
	queue<pair<int,int> > a;
	int t;
	pair<int,int> s1,s2;
	for(int i=0;i<n;i++)
	{
		cin>>t;
		a.push(make_pair(t,i));
	}
	while(a.size()!=2)
	{
		s1 = a.front();
		a.pop();
		s2 = a.front();
		a.pop();
		if(s1.first>s2.first) a.push(s1);
		else a.push(s2);
	}
	s1 = a.front();
	a.pop();
	s2 = a.front();
	a.pop();
	if(s1.first>s2.first) cout<<s2.second+1;
	else cout<<s1.second+1;
}

P4913 【深基16.例3】二叉树深度

思路

先建树（用vector），找到根节点后dfs

实现

最近的代码写的有点子烂

#include<bits/stdc++.h>
using namespace std;
int n,ans;
typedef struct
{
	int l;
	int r;
}node;
vector<node> a;
void dfs(int root,int depth)
{
	ans = max(ans,depth);
	if(a[root].l)
	{
		dfs(a[root].l,depth+1);
	}
	if(a[root].r)
	{
		dfs(a[root].r,depth+1);
	}
}
int main()
{
	cin>>n;
	node t;
	int t1,t2;
	a.push_back(t);
	vector<bool> isroot(n+1,1);
	for(int i=1;i<=n;i++)
	{
		cin>>t1>>t2;
		isroot[t1] = 0;
		isroot[t2] = 0;
		t.l = t1;
		t.r = t2;
		a.push_back(t);
	}
	int i;
	for(i=1;i<=n;i++)
	{
		if(isroot[i])
		break;
	}
	dfs(i,1);
	cout<<ans;
}

P1364 医院设置

思路

• 树本身是一种图，在树中一个点到另一个点的路径是唯一的。比较暴力的做法就是枚举每一个可能建医院的点，通过bfs算出值。

实现

#include<bits/stdc++.h>
using namespace std;
int n;
int ans = 10e7;
typedef struct
{
	int index;
	int weight;
	int depth;
}node;

int bfs(int root,vector<bool> & vis,vector<vector<int> > &G,vector<int> &w)
{
	int weight = 0;
	node t;
	queue<node>q;
	t.index = root;
	t.weight = w[root];
	t.depth = 0;
	q.push(t);
	while(!q.empty())
	{
		if(vis[q.front().index])
		{
			q.pop();
			continue;
		}
		vis[q.front().index] = 1;
		weight += q.front().depth * q.front().weight;
		//cout<<"root:"<<root<<"q.front().index and depth and weight "<<q.front().index<<" "<<q.front().depth<<" "<<q.front().weight<<endl;
		int ind = q.front().index;
		int d = q.front().depth;
		q.pop();
		for(int i=0;i<G[ind].size();i++)
		{
			t.index = G[ind][i];
			if(vis[t.index]) continue;
			t.weight = w[t.index];
			t.depth = d+1;
			
			q.push(t);
		}	
	}
//	cout<<"w:"<<weight<<endl;
	return weight;
}
int main()
{
	cin>>n;
	
	vector<vector<int> > G(n);
	vector<int> w(n);
	int t1,t2;
	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>t1>>t2;
		if(t1!=0)
		{
		G[i].push_back(t1-1);
		G[t1-1].push_back(i);
		}
		if(t2!=0)
		{
		G[i].push_back(t2-1);
		G[t2-1].push_back(i);
		}
	}
	for(int i=0;i<n;i++)
	{
		vector<bool> vis(n,0);
		ans = min(ans,bfs(i,vis,G,w));
	}
	cout<<ans; 
}

其他

• 题解区讲到求树的重心的做法：

来自 Huawei360

P1229 遍历问题

思路

来自洛谷题解区 青丝、暮成雪

只有一个儿子 的节点 才会在知道 前序后序 的情况下有不同的中序遍历，所以将题目转化成找 只有一个儿子的节点个数。
可以很容易的找出这类节点在前序后序中出现的规律。（前序中出现AB，后序中出现BA，则这个节点只有一个儿子）
每个这类节点有两种中序遍历（及儿子在左，儿子在右）根据乘法原理中序遍历数为 2^节点个数 种

实现

#include<bits/stdc++.h>
using namespace std;
int ans;
char str1[233],str2[233];
int main()
{
        scanf("%s",str1);
        scanf("%s",str2);
        for(int i=0;i<strlen(str1);i++)
         for(int j=1;j<strlen(str2);j++)
          if(str1[i]==str2[j]&&str1[i+1]==str2[j-1])
           ans++;
        printf("%d",1<<ans);
        return 0;
}

P3884 [JLOI2009]二叉树问题

思路

比较暴力，Floyd得出每两个顶点之间的最短距离。深度就是1号节点到其他所有点的距离中的最大值。宽度就是距离1号节点距离相同的点的最大个数，通过一个桶来计数。
有空再琢磨一下LCA/树链

实现

#include<bits/stdc++.h>
#define inf INT_MAX/4
using namespace std;
int n;
int G[110][110];
int tong[110];
int main()
{
	cin>>n;
	int t1,t2;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j) G[i][j] = inf;
		}
	}
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&t1,&t2);
		G[t1][t2] = 1;
		G[t2][t1] = 2;
	}
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                 G[i][j]=min(G[i][j],G[i][k]+G[k][j]);//Floyd算法
	//求深度
	int depth = 0;
	
	for(int i=2;i<=n;i++)
	{
		depth = max(depth,G[1][i]);
		tong[G[1][i]]++;
	 } 
	 //求宽度
	 int width = 0; 
	 for(int i=0;i<=depth;i++)
	 {
	 	width = max(width,tong[i]);
	 }
	 cout<<depth+1<<endl;
	 cout<<width<<endl;
	 int x,y;
	 cin>>x>>y;
	 cout<<G[x][y];
}

欢迎指正-