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）怎麼實作判斷二叉排序樹的鏡像的先序？不妨可以試試其與二叉排序樹有什麼關聯。親自試驗之後，你會發現其實鏡像就是二叉排序樹的另外的幾種輸出方式罷了！