# PAT 解题报告 1064. Complete Binary Search Tree (30)

### 题目描述：

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

### 算法分析：

(1) 对数组排序, 把整个数组push到queue里面(可以用小的结构代表数组, 比如起始index + 终止index就可以代表一个数组段)

(2) 因为必须是CBT, 那么其实排序好的这个数组中哪一个element是root其实是确定的, 利用CBT的性质, 推算出root的index, 输出该root的数值, 同时这个index把数组分割成了左右子树, 把左右子树push到queue里面

(3) pop queue, 利用(2)同样的方法递归处理子树, 知道queue空了为止

### 注意点：

Written on September 2, 2013