简单二叉树
1.首先是树的遍历问题 ：
树的先序 中序 后序遍历 主要就是中序决定了这颗树长什么样，中序找根分为左右子树，然后再不断去查找 ！！！这个点挺重要的。如果是知道前序和后序而不知道根的话那就会出问题！！ 因为当子节点只有一个时有两种情况！！
#include <bits/stdc++.h>
using namespace std;
int main()
{
char a[1005];
char b[1005];
cin>>a>>b; //这个就是求有多少种主要就是想明白什么情况会有多种答案
int i,j;
int len1=strlen(a);
int len2=strlen(b);
int cnt=0;
for(i=0;i<=len1;i++)
{
for(j=1;j<=len2;j++)
if(a[i]==b[j]&&a[i+1]==b[j-1])
cnt++;
}
cout<<pow(2,cnt);
}
2.中序和前序求后序
这就是找根分割！！！
#include <bits/stdc++.h>
using namespace std;
string a,b;
void dfs(string a,string b)
{
if(a.empty()||b.empty()) return ;
char c=a[0]; 这个是第一个根！！
int k=b.find(c); 然后找根分子树
string b1=b.substr(0,k); 切割
string b2=b.substr(k+1); 切割
a.erase(a.begin());
string a1=a.substr(0,k);
string a2=a.substr(k);
dfs(a1,b1);左子树
dfs(a2,b2);右子树
cout<<c; 最后输出符合条件！！
}
int main()
{
cin>>a>>b;
dfs(b,a);
}
求子树和
用记忆化搜索去跑 整个树这样就能求解出来！！
int solve(int x)
{
int sum=a[x].v;
if(a[x].l) sum+=solve(a[x].l);
if(a[x].r) sum+=solve(a[x].r);
v[x]=sum;
return sum;
}
树上路径
就是去跑一遍每一个节点用一个from数组去记录，也是一个搜索然后倒序输出。从u到v直接倒序输出！！
dfs(u)；//跑一整个树搜索完！！
for(i=v;i!=u;i=from[i])
{
ans[++len]=i;
}
ans[++len]=u;
for(i=len;i;i--)
printf("%d ",ans[i]);
树的直径
dfs(1);//先跑一遍 找到距离最远的！！
for(i=1;i<=n;i++)
{
if(v<dist[i])
idx=i,v=dist[i];
}
memset(dist,0,sizeof(dist));
memset(from,0,sizeof(from));
from[idx]=-1;
dfs(idx);//再跑一遍找到距离最远的这时求的距离便是直径！！
只有在直径上跑才是最远的情况！！！可以仔细想想最远一定是先到直径所在的边的与直径相交的点加上离直径最远的点上。
树的中心
性质：到其他点的最长路径最短 以树的中心为整棵树的根时，从该根到每个叶子节点的最长路径最短
树的中心为树直径的中点！！ 当点数为奇数时中点唯一当点数为偶数时点数不唯一
暂时没找到应用！！！
树的重心
1.当一个节点被选择成为根节点，它底下每个子节点的子树的大小（子树包含的节点数目）最大值最小的那个节点，被称为树的重心：
注 ： 一棵树可能有1个或两个重心
性质：
1.以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
2.树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
3.把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
4.在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> edge[100001];
int s[100001],from[100001],dist[100001];
void solve(int x)
{
s[x]=1;
for(auto y:edge[x])
{
if(y!=from[x])//找到子节点
{
from[y]=x;
solve(y);//先去解决儿子子树！！
s[x]+=s[y];
}
}
} 这样来得出所有子树的大小！！
void dfs(int x)
{
for(auto y:edge[x])
{
if(y!=from[x])
{
from[y]=x;
dist[y]=dist[x]+1;//去找中心应该是！！
dfs(y);
}
} 得出所有点以某点为根时的距离
}
int main()
{
scanf("%d",&n);
int i;
for(i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
edge[x].push_back(y);
edge[y].push_back(x);//建立无向边 无根树！！
}
from[1]=-1;
solve(1);//求以1为根时所有的子树的大小！！
int v=1<<30,idx=0;
for(i=1;i<=n;i++)//找出最大子树最小的节点
{
int f=0;
for(auto y:edge[i])
{
if(y!=from[i])//儿子
f=max(f,s[y]);
else f=max(n-s[i],f); //求最大子树！！该点所连出去的最大子树 //变向的父亲用所有的减去该子树的大小就是外面那颗子树！！
}
if(v>f)
{
v=f;
idx=i; // 找到那个重心！！！用性质去找重心
} //因为该条件是充分必要条件！！！
}
from[idx]=-1;//最好这里要重新初始化一遍！！！！但是不用也可！
dfs(idx);
long long ans=0;
for(i=1;i<=n;i++)
ans+=dist[i];
printf("%lld",ans);
}
典型题目！！！ http://oj.daimayuan.top/course/7/problem/530
树上 LCA 非常非常典型！！！
直接来一个最终版本！！！
先简单介绍一些比较不适用的做法：1.最大公共后缀 找到两个节点同时找到根路径，从后往前找最深的那个点。
2.让两点先跳到同一点！！然后一起往上跳！！直到跳到同一点！
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> edge[100001];
int father[100001][20],dist[100001];
void solve(int x)
{
for(auto y:edge[x])
{
dist[y]=dist[x]+1;
solve(y);
}
}
int main()
{
scanf("%d",&n);
int i,j;
for(i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
edge[x].push_back(y);
father[y][0]=x;
}
for(j=1;j<20;j++)// 利用倍增求出所有点的父亲节点 19 次方差不多50多个W 个点！！
for(i=1;i<=n;i++)
{
if(father[i][j-1])
father[i][j]=father[father[i][j-1]][j-1];
}
solve(1);
scanf("%d",&m);// m 个 询 问
for(i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(dist[x]<dist[y]) swap(x,y);
int z=dist[x]-dist[y];
for(int j=0;j<20&&z;j++,z/=2)//用二进制不断来跳！！ 应该是跳到同一高度！！
{
if(z&1) x=father[x][j];
}
if(x==y)
{
printf("%d\n",x);
continue;
}
for(j=19;j>=0;j--)
{
if(father[x][j]!=father[y][j])
x=father[x][j],y=father[y][j];
}
printf("%d\n",father[x][0]);// 7:4 +2 +1 8 : 4 + 2 +1 +1 这个挺牛的！！！
}
}