1123 Is It a Complete AVL Tree (30分)

快来打我* 2023-02-08 15:52 50阅读 0赞

[1123 Is It a Complete AVL Tree (30分)][1123 Is It a Complete AVL Tree _30]  
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.  
![在这里插入图片描述][20200725094218796.png]  
Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

**Input Specification:**  
Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

**Output Specification:**  
For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print YES if the tree is complete, or NO if not.

**Sample Input 1:**

5
    88 70 61 63 65

**Sample Output 1:**

70 63 88 61 65
    YES

**Sample Input 2:**

8
    88 70 61 96 120 90 65 68

**Sample Output 2:**

88 65 96 61 70 90 120 68
    NO

#include<bits/stdc++.h>
    using namespace std;
    vector<int> vi;
    bool flag=true;
    struct node{ 
    	int val,height;
    	node *lc,*rc;
    	node(int v){ 
    		val=v;
    		height=1;
    		lc=NULL;
    		rc=NULL;
    	}
    };
    int getHeight(node *root){ 
    	if(root==NULL)return 0;
    	else return root->height;
    } 
    void updateHeight(node *&root){ 
    	root->height=max(getHeight(root->lc),getHeight(root->rc))+1;
    }
    int getBalanceFactor(node *root){ 
    	return getHeight(root->lc)- getHeight(root->rc);
    } 
    void L(node *&root){ 
    	node *temp =root->rc;
    	root->rc=temp->lc;
    	temp->lc=root;
    	updateHeight(root);
    	updateHeight(temp);
    	root = temp; 
    }
    void R(node *&root){ 
    	node *temp=root->lc;
    	root->lc=temp->rc;
    	temp->rc=root;
    	updateHeight(root);
    	updateHeight(temp);
    	root=temp;
    }
    void insert(int v,node *&root){ 
    	if(root==NULL){ 
    		root=new node(v);
    		return;
    	}
    	if(v==root->val){ 
    		return;
    	}else if(v < root->val){ 
    		insert(v,root->lc);
    		updateHeight(root);
    		if(getBalanceFactor(root)==2){ 
    			if(getBalanceFactor(root->lc)==1){ 
    				R(root);
    			}else if(getBalanceFactor(root->lc)==-1){ 
    				L(root->lc);
    				R(root);
    			}
    		}
    	}else{ 
    		insert(v,root->rc);//往右子树插入 
    		updateHeight(root);
    		if(getBalanceFactor(root) == -2){ 
    			if(getBalanceFactor(root->rc) == -1){ //RR型
    				L(root); 
    			}
    			else if(getBalanceFactor(root->rc) == 1){ //RL型
    				R(root->rc);
    				L(root); 
    			}
    		}
    	}
    }
    node *create(vector<int> &vi){ 
        node*root = NULL;
        for(int i=0;i<vi.size();i++){ 
        	insert(vi[i],root);
    	}
    	return root;
    }
    void lev(node *root){ 
    	if(root==NULL)return;
    	queue<node*> q;
    	q.push(root);
    	bool cc=true;
    	while(!q.empty()){ 
    		node* now = q.front();
    		if(cc){ 
    			cout<<now->val;
    			cc=false;
    		}else 	cout<<" "<<now->val;
    		q.pop();
    		if(now->lc!=NULL) q.push(now->lc);
    		if(now->rc!=NULL) q.push(now->rc);
    	}
    }
    bool dfs(node *root){ 
    	if(root==NULL)return false;
    	queue<node*> q;
    	q.push(root);
    	while(!q.empty()){ 
    		node *now = q.front();
    		q.pop();
    		if(now->lc&&now->rc){ 
    			q.push(now->lc);
    			q.push(now->rc);
    		}else if(now->lc==NULL && now->rc) { 
    			return false;
    		}else { 
    			 if(now->rc==NULL && now->lc)q.push(now->lc);
    			 while(!q.empty()){ 
                            node *p = q.front(); q.pop();
                            if(p->lc || p->rc)
                            return false;
                 }    
    		}
    	}
    	return true;
    }
    int main(){ 
    	int k,n;
    	cin>>n;
    	for(int i=0;i<n;i++){ 
    		cin>>k;
    		vi.push_back(k);
    	}
    	node *root = create(vi);
        lev(root);
        cout<<endl;
     
        if(dfs(root))cout<<"YES";
        else cout<<"NO";
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70]

[1123 Is It a Complete AVL Tree _30]: https://pintia.cn/problem-sets/994805342720868352/problems/994805351302414336
[20200725094218796.png]: /images/20230208/60e512fc574e47ebbeae5aa1d89d6437.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200725094134968.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3,size_16,color_FFFFFF,t_70