首先是建立二叉平衡树,
然后是层序遍历,注意判断是否是完全树的条件:
当发现某个节点的孩子为空时,以后如果发现某个节点存在孩子,那么就不是完全二叉树.
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode{
int val{};
TreeNode* left{};
TreeNode* right{};
int height=0;
};
int Height(TreeNode* root){
if(root== nullptr){
return -1;
}
return root->height;
}
TreeNode* rightRotate(TreeNode *root){
TreeNode* L=root->left;
root->left=L->right;
L->right=root;
root->height=max(Height(root->left),Height(root->right))+1;
L->height=max(Height(L->left),Height(L->right))+1;
return L;
}
TreeNode* leftRotate(TreeNode *root){
TreeNode* R=root->right;
root->right=R->left;
R->left=root;
root->height=max(Height(root->left),Height(root->right))+1;
R->height=max(Height(R->left),Height(R->right))+1;
return R;
}
TreeNode* leftRightRotate(TreeNode *root){
root->left= leftRotate(root->left);
return rightRotate(root);
}
TreeNode* rightLeftRotate(TreeNode *root){
root->right= rightRotate(root->right);
return leftRotate(root);
}
TreeNode* constructTree(TreeNode* root,int val){
if(root==nullptr){
root=new TreeNode();
root->val=val;
return root;
}
if(val<root->val){
root->left=constructTree(root->left,val);
} else{
root->right=constructTree(root->right,val);
}
if(Height(root->left)-Height(root->right)==2){
if(val<root->left->val){
root= rightRotate(root);
} else{
root= leftRightRotate(root);
}
}
if(Height(root->right)-Height(root->left)==2){
if(val>root->right->val){
root= leftRotate(root);
} else{
root= rightLeftRotate(root);
}
}
//更新根节点的高度信息
root->height=max(Height(root->left),Height(root->right))+1;
return root;
}
bool isComplete=true;
//如果发现存在有为空孩子的节点,继续遍历过程中仍然发现存在有孩子不为空的节点,那么就不是一个完全二叉树
vector<int> levelOrder(TreeNode* root){
queue<TreeNode* > queue1;
vector<int> res;
queue1.push(root);
bool hasNull=false;
while(!queue1.empty()){
auto node=queue1.front();
res.push_back(node->val);
queue1.pop();
if(node->left== nullptr){
hasNull= true;
} else{
if(hasNull) {
isComplete = false;
}
queue1.push(node->left);
}
if(node->right== nullptr){
hasNull= true;
} else{
if(hasNull){
isComplete= false;
}
// res.push_back(node->val);
queue1.push(node->right);
}
}
return res;
}
int main() {
int N;
cin>>N;
TreeNode* root= nullptr;
for (int i = 0; i < N; ++i) {
int val;
cin>>val;
root=constructTree(root,val);
}
auto res=levelOrder(root);
cout<<res[0];
for (int i = 1; i < res.size(); ++i) {
cout<<" "<<res[i];
}
cout<<endl;
if(isComplete){
cout<<"YES"<<endl;
} else{
cout<<"NO"<<endl;
}
return 0;
}