AKSZ-图
2024-06-16 16:27:31
发布于:广东
AKSZ - 图
满x叉树节点数
图的度
一个顶点的(无向图不算入度)
出度就是出去的路径数,而入度是进入的路径数
二叉树的性质
如果叶子数量为,度2数量为,则
有个结点的完全二叉树深度为
1、ruoi=1,i为根,无父
2、i>1,i的父节点为
3、若2i>n,则i要么没有左孩子,要么左孩子是2i
4、若2i+1>n,则i要么没有右孩子,要么右孩子是2i+1
先序
先访问根节点再访问左子树,接着访问右子树
中序(左根右)
后序(左右根)
中后求前
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N],b[N],c[N];
void f(int l1,int r1,int l2,int r2){
//边界
if(l1==r1){
cout<<a[l1]<<' ';
return;
}
//递归划分
int root=b[r2]; //找到根
//在中序找根
int pos=c[root];
cout<<root<<' ';
int len1=pos-l1;
int len2=r1-pos;
if(pos-1>=l1)f(l1,pos-1,l2,l2+len1-1);
if(pos+1<=r1)f(pos+1,r1,r2-len2,r2-1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
c[a[i]]=i;
}
for(int j=1;j<=n;j++) cin>>b[j];
f(1,n,1,n);
return 0;
}
这里空空如也
有帮助,赞一个