pat 1043

1.pat 1043是一道有质量的二叉树题目

2.题意分析

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.

【左右子树必须都是二叉排序树】

If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.

【如果我们调换左右子树的每个节点，我们将得到的新二叉树称为二叉树的镜像】

Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.

【现在，给出一串整数，你将判断其是否是二叉树或者是二叉树的镜像的先序遍历序列】

Input Specification:

【输入解释】

Each input file contains one test case. For each case, the first line contains a positive integer N (<=1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.

【每个输入文件包含一个测试用例，对于每个测试用例，第一行是一个小于1000的正整数N。接着下一行会给出N个正整数，所有的数是被一个空格分割】

Output Specification:

【具体输出】

For each test case, first print in a line "YES" if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or "NO" if not. Then if the answer is "YES", print in the next line the postorder traversal sequence of that 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.

【对于每个测试用例，第一行打印“YES”,，如果序列是二叉排序树或者是二叉排序树镜像的先序遍历，然后在下一行输出那个树的后序遍历序列；如果不是先序序列，则输出“NO”】

我甚是“无聊”，于是将这题目的所有描述都给粘贴过来了。并且将其翻译成了中文。

3.源代码

4.总结

需要注意的地方有以下几处：

（1）如果不使用递归的手法，你会建立一棵二叉排序树么？想想在建立二叉排序树的关键是什么！

（2）怎么实现判断二叉排序树的镜像的先序？不妨可以试试其与二叉排序树有什么关联。亲自试验之后，你会发现其实镜像就是二叉排序树的另外的几种输出方式罢了！