【PAT】【Advanced Level】1123. Is It a Complete AVL Tree (30)

本文主要是介绍【PAT】【Advanced Level】1123. Is It a Complete AVL Tree (30)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1123. Is It a Complete AVL Tree (30)

原题链接：

https://www.patest.cn/contests/pat-a-practise/1123

思路：

首先平衡树

然后判断是否是满的平衡树

由于是平衡树

所以叶节点一定在最后两层

判断条件：

所有倒数第二层的叶节点在 中序遍历 序列中 一定在   层序遍历最后一个节点  的后边。

不能存在左子树为空的非叶节点

右子树为空的非叶节点一定是 层序遍历最后一个节点 的父亲

CODE：

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;typedef struct S
{int ind;int val;int ls;int rs;int ld;int rd;int fl;int tra;
};
vector<S> T;
int trav;
vector<S> ro;
vector<S> le;void left(int n)
{S s1=T[n];S s2=T[T[n].rs];T[n].ind=n;T[n].val=s2.val;T[n].rs=s2.rs;T[n].ls=s2.ind;T[n].rd=s2.rd;T[n].ld=max(s1.ld,s2.ld)+1;T[s2.ind].ind=s2.ind;T[s2.ind].val=s1.val;T[s2.ind].rs=s2.ls;T[s2.ind].ls=s1.ls;T[s2.ind].rd=s2.ld;T[s2.ind].ld=s1.ld;}
void right(int n)
{S s1=T[n];S s2=T[T[n].ls];T[n].ind=n;T[n].val=s2.val;T[n].ls=s2.ls;T[n].rs=s2.ind;T[n].ld=s2.ld;T[n].rd=max(s1.rd,s2.rd)+1;T[s2.ind].ind=s2.ind;T[s2.ind].val=s1.val;T[s2.ind].ls=s2.rs;T[s2.ind].rs=s1.rs;T[s2.ind].ld=s2.rd;T[s2.ind].rd=s1.rd;}
int insert(int n,int v)
{if (v<T[n].val){if (T[n].ls==-1){S s;s.ind=T.size();s.val=v;s.ls=s.rs=-1;s.ld=s.rd=0;T[n].ls=T.size();T[n].ld=1;T.push_back(s);}else{int fl=insert(T[n].ls,v)+1;T[n].ld=fl;}}else{if (T[n].rs==-1){S s;s.ind=T.size();s.val=v;s.ls=s.rs=-1;s.ld=s.rd=0;T[n].rs=T.size();T[n].rd=1;T.push_back(s);}else{int fl=insert(T[n].rs,v)+1;T[n].rd=fl;}	}if (T[n].ld-T[n].rd>1){if (T[T[n].ls].rd>T[T[n].ls].ld){left(T[n].ls);}right(n);}else if (T[n].rd-T[n].ld>1){//cout<<v<<" "<<T[n].val<<" "<<T[n].ld<<" "<<T[n].rd<<endl;if (T[T[n].rs].ld>T[T[n].rs].rd){right(T[n].rs);}left(n);}//cout<<v<<" "<<T[n].val<<" "<<T[n].ld<<" "<<T[n].rd<<endl;return max(T[n].ld,T[n].rd);
}
void dfs(int n,int flo)
{T[n].fl=flo;if (T[n].ls!=-1)	dfs(T[n].ls,flo+1);T[n].tra=trav;trav++;if (T[n].rs!=-1)	dfs(T[n].rs,flo+1);
}bool cmp(S a, S b)
{if (a.fl==b.fl){return a.tra<b.tra;}else{return a.fl<b.fl;}	
}
int main()
{int n;cin>>n;S s;s.ind=0;s.ls=s.rs=-1;s.ld=s.rd=0;cin>>s.val;T.push_back(s);for (int i=1;i<n;i++){int t;cin>>t;insert(0,t);}	trav=0;dfs(0,0);sort(T.begin(),T.end(),cmp);bool flag=0;for (int i=0;i<n;i++){if (i!=0) cout<<" ";cout<<T[i].val; if ( (T[i].ls==-1&&T[i].rs==-1) && (T[i].fl==T[n-1].fl-1) && (T[i].tra<T[n-1].tra)){flag=1;}if ( (T[i].ls==-1&&T[i].rs!=-1)){flag=1;}if ( (T[i].ls!=-1&&T[i].rs==-1) && (T[i].ls!=T[n-1].ind) ){flag=1;}}cout<<endl;if (flag==0)	cout<<"YES";else	cout<<"NO";return 0;
}

这篇关于【PAT】【Advanced Level】1123. Is It a Complete AVL Tree (30)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---