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.

求一颗完全二叉搜索树的level order顺序遍历.


仔细想的话这个题目其实也可以做, 利用queue进行层次遍历, 同时递归构建CBT:

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

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

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

因为queue的性质, 所以输出的结构就是层次遍历的结果.


上述方法有一些小trick,  递归输出的base case 分成三种, 比较不容易出错, 元素个数1 到 3的数组段对应的CBT的结构是唯一确定的, 而且和上面步骤(2)找root index是不同的, 于是可以单独当成base case处理, 减少出错.

Written on September 2, 2013