#1043. Is It a Binary Search Tree【二叉搜索树 + 树的遍历】

Problem Description：

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$ ($\le 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

Problem Analysis:

前置知识：

二叉搜索树的中序遍历是所有节点的权值按从小到大的排列，而其镜像树的中序遍历是所有节点的权值按从大到小的排列。

有了这个前置知识，我们在得到其节点权值的前序遍历同时，也可以得到它的中序遍历或者其镜像树的中序遍历，我们可以递归建树，并在这个过程中判断能否建树成功，若能建树成功，则输出其后序遍历：

bool build(int il, int ir, int pl, int pr, int type)
{
    if (il > ir) return true;
    
    int root = preorder[pl];
    int k;
    if (type == 0) // 前序遍历
    {
        for (k = il; k <= ir; k ++ ) // 找到root在中序遍历中的位置
            if (root == inorder[k])
                break;
        if (k > ir) return false;
    }   
    else
    {
        for (k = ir; k >= il; k -- )
            if (root == inorder[k])
                break;
        if (k < il) return false;
    }
    bool res = true;
    if (!build(il, k - 1, pl + 1, pl + k - il, type)) res = false;
    if (!build(k + 1, ir, pl + k - il + 1, pr, type)) res = false;
    postorder[cnt ++ ] = root;
    return res;
}

需要注意的是，这里由于权值大小并不是都是唯一的，可能存在权值相同的节点，因此我们在根据前序遍历建树过程中，在 inorder[] 中查询根节点 root 的位置 k 时，需要从左往右找，即按 il 向 ir 的方向扫描，因为二叉搜索树必须满足左子树的权值大小严格小于根节点权值，右子树权值大小严格大于等于根节点权值；同理其镜像树需要按 ir 向 il 的方向扫描。

详细过程见代码。

Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int preorder[N], inorder[N];
int postorder[N], cnt;

bool build(int il, int ir, int pl, int pr, int type)
{
    if (il > ir) return true;
    
    int root = preorder[pl];
    int k;
    if (type == 0)
    {
        for (k = il; k <= ir; k ++ ) // 找到root在中序遍历中的位置
            if (root == inorder[k])
                break;
        if (k > ir) return false;
    }   
    else
    {
        for (k = ir; k >= il; k -- )
            if (root == inorder[k])
                break;
        if (k < il) return false;
    }
    
    bool res = true;
    if (!build(il, k - 1, pl + 1, pl + k - il, type)) res = false;
    if (!build(k + 1, ir, pl + k - il + 1, pr, type)) res = false;
    
    postorder[cnt ++ ] = root;
    return res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) 
    {
        cin >> preorder[i];
        inorder[i] = preorder[i];
    }
    
    sort(inorder, inorder + n);
    
    if (build(0, n - 1, 0, n - 1, 0))
    {
        puts("YES");
        cout << postorder[0];
        for (int i = 1; i < n; i ++ )
            cout << ' ' << postorder[i];
        cout << endl;
    }
    else 
    {
        cnt = 0;
        reverse(inorder, inorder + n);
        if (build(0, n - 1, 0, n - 1, 1))
        {
            puts("YES");
            cout << postorder[0];
            for (int i = 1; i < n; i ++ )
                cout << ' ' << postorder[i];
            cout << endl;
        }
        else puts("NO");
    }
    return 0;
}