L3-010 是否完全二叉搜索树 （30 分）

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

输入格式：

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

输出格式：

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。

输入样例1：

1
2
9
38 45 42 24 58 30 67 12 51

输出样例1：

1
2
38 45 24 58 42 30 12 67 51
YES

输入样例2：

1
2
8
38 24 12 45 58 67 42 51

输出样例2：

1
2
38 45 24 58 42 12 67 51
NO

一道考察二叉树插入方法例程，层序遍历，判断是否为一棵完全二叉树的综合题。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<vector>
#include<queue>

using namespace std;


struct TreeNode{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; 

void insertNode(TreeNode* root, int val){
	if(root == NULL){
		return;
	}
	if(root->val < val){
		if(root->left == NULL){
			TreeNode* now = new TreeNode(val);
			root->left = now;
		}else{
			insertNode(root->left, val);
		}
	}else if(root->val > val){
		if(root->right == NULL){
			TreeNode* now = new TreeNode(val);
			root->right = now;
		}else{
			insertNode(root->right, val);
		}
	}
}

void levelOrder(TreeNode* root){
	queue<TreeNode*> q;
	q.push(root);
	bool isfirst = true;
	while(!q.empty()){
		TreeNode* node = q.front();
		q.pop();
		if(isfirst){
			cout << node->val;
			isfirst = false;
		}else{
			cout <<  " " << node->val;
		}
		if(node->left) {
			q.push(node->left);
		}
		if(node->right) {
			q.push(node->right);
		}
		
	}
}

bool isCST(TreeNode* root){
	bool leaf = false;
	queue<TreeNode*> q;
	q.push(root);
	while(!q.empty()){
		TreeNode* node = q.front();
		q.pop();
		if(node->right && !node->left) return false;
		if(leaf && (node->left || node->right)) return false;
		if(!node->right && !leaf){
			leaf = true;
		}
		if(node->left) {
			q.push(node->left);
		}
		if(node->right) {
			q.push(node->right);
		}
	}
	return true;
}

void printTree(TreeNode* root){
	if(!root) return;
	printTree(root->left);
	cout << " " << root->val;
	printTree(root->right);
}

int main(){
	int c;
	cin >> c;
	int rootval;
	cin >> rootval;
	TreeNode* root = new TreeNode(rootval);
	for(int i = 1; i < c; i++){
		int nodeval;
		cin >> nodeval;
		insertNode(root, nodeval);
	}
	levelOrder(root);
	cout << endl;
	if(isCST(root)){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
	
	return 0;
}