PAT甲级：1043 Is It a Binary Search Tree

题目描述：

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.

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.

Sample Input 1:

7
8 6 5 7 10 8 11

Sample Output 1:

YES
5 7 6 8 11 10 8

Sample Input 2:

7
8 10 11 8 6 7 5

Sample Output 2:

YES
11 8 10 7 5 6 8

Sample Input 3:

7
8 6 8 5 10 9 11

Sample Output 3:

NO

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

题目大意： 

给定一个序列，问这个序列是否能构成某个二叉搜索树或者其镜像的前序遍历，输出为是否能构成，如果能构成输出后序遍历。

解题思路： 

这里只讲解是BST的情况，镜像树的情况只需要将BST的判断条件反过来即可。

首先根据BST的性质，我们知道对于一颗树的根节点而言，左子树的所有点都比它小，右子树的所有点都比它大。而题目给定了一个树的前序遍历，即遍历顺序是：根-左子树-右子树

那么也就是说 在给定的前序遍历数组中 第一个点是根结点 二根节点后连续的一段比根节点小的点就是左子树，剩下的一段是右子树。我们分开遍历左右子树，再将根结点放入队列中，得到的就是后序遍历。

注意：得到后序遍历队列后 我们需要验证一下它的长度是否等于总数N，因为有可能它不是一颗BST或者镜像树，导致上述黑体判断子树部分出错。

分别判断BST和镜像树能否对应这个前序遍历即可，两者有一个成功就可以。

Python3代码： 

import sys
sys.setrecursionlimit(1000000)
N = int(input())
lst = list(map(int,input().split()))
ans = []

def check(l,r,isBST) :
    global ans
    if l > r : return
    lc = r ; rc = l + 1
    if isBST : # 为BST的情况
        while lc > l and lst[lc] >= lst[l] : lc -= 1
        while rc <= r and lst[rc] < lst[l] : rc += 1
    else : # 为镜像树的情况
        while lc > l and lst[lc] < lst[l] : lc -= 1
        while rc <= r and lst[rc] >= lst[l] : rc += 1
    if lc + 1 != rc : return # 如果既不是BST也不是镜像树就返回
    check(l+1,lc,isBST)
    check(rc,r,isBST)
    ans.append(lst[l])
    
check(0,N-1,1) 
if len(ans) != N : # 看是否成功
    ans = []
    check(0,N-1,0)
if len(ans) != N : print('NO')
else :
    print('YES')
    for i in range(N) : print(ans[i],end=' ') if i != N-1 else print(ans[i])

分享一篇非常赞的题解： AcWing 1527. 超级走心的题解，真的。天梯二叉搜索树题解。 - AcWing