PAT 1043 Is It a Binary Search Tree[二叉树][难]

1043 Is It a Binary Search Tree（25 分）

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

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

题目大意：如初一系列数，如果它是给出一棵二叉搜索树的前根遍历或者是它的左右子数反转的二叉树的前根便利（关键字会重复出现），那么就输出Yes，并且输出这棵二叉树的后根遍历，如果不是输出No。

//建立一棵树，存储，使用数组存储。

代码来自:https://www.liuchuo.net/archives/2153

#include <cstdio>
#include <vector>
using namespace std;
bool isMirror;
vector<int> pre, post;
void getpost(int root, int tail) {
    if(root > tail) return ;
    int i = root + 1, j = tail;
    if(!isMirror) {
        while(i <= tail && pre[root] > pre[i]) i++;
        //这个i一直循环到右子树的根节点，因为root的右子树是>pre[root]的。
        while(j > root && pre[root] <= pre[j]) j--;
        //这个是找到左子树前序遍历的最后一个节点。
    } else {
        while(i <= tail && pre[root] <= pre[i]) i++;
        while(j > root && pre[root] > pre[j]) j--;
    }
    if(i - j != 1) return ;
    getpost(root + 1, j);//遍历左子树，
    getpost(i, tail);//遍历右子树
    post.push_back(pre[root]);//后根遍历放进来。
    //当时叶节点的时候，会在入口处的if直接return了。
}
int main() {
    int n;
    scanf("%d", &n);
    pre.resize(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &pre[i]);//输入前序。
    getpost(0, n - 1);//获取后序，
    if(post.size() != n) {
        isMirror = true;
        post.clear();
        getpost(0, n - 1);
    }
    if(post.size() == n) {//如果是正常搜索二叉树的话，应该是=n的，有这么个规律在的。
        printf("YES
%d", post[0]);//0直接在这里输出。
        for(int i = 1; i < n; i++)
            printf(" %d", post[i]);
    } else {
        printf("NO");
    }
    return 0;
}

//柳神的应该是能AC的代码中最精简的了，不用建树，厉害，之前也见到过这样的题目，应该加深一下，学习了。

//正常来说的思路就是，建树，所以参考了以下代码，也十分整洁：https://www.nowcoder.com/questionTerminal/8bcd661314744321b55dce1c1bfa8c54

//全是套路==
#include <cstdio>
#include <vector>
using namespace std;
struct Node{
    int value;
    Node *left, *right;//用的是指针哟。
};

void Insert(Node* &root, int data){//今天自己建树不成功才发现， 原来这位大佬传的是指针的引用，只传指针是不行的，学习了！2018-9-7
    if(root == NULL){
        root = new Node;//新指向一个节点。
        root -> value = data;
        root -> left = NULL;
        root -> right = NULL;
        return;
    }
    if(data < root->value) Insert(root->left, data);
    else Insert(root->right, data);//由此看来>=root都是放在右子树的。
}

void PreOrder(Node* root, vector<int>& v){
    if(root == NULL) return;
    v.push_back(root->value);//先访问根节点，再左右子树。
    PreOrder(root->left, v);
    PreOrder(root->right, v);
}

void PreMirrorOrder(Node* root, vector<int>& v){
    if(root == NULL) return;
    v.push_back(root->value);
    PreMirrorOrder(root->right, v);
    PreMirrorOrder(root->left, v);
}

void PostOrder(Node* root, vector<int>& v){//注意这里传了引用，其实也可以将其设置为全局变量。
    if(root == NULL) return;
    PostOrder(root->left, v);
    PostOrder(root->right, v);
    v.push_back(root->value);
}

void PostMirrorOrder(Node* root, vector<int>& v){
    if(root == NULL) return;
    PostMirrorOrder(root->right, v);//既然右边小，那么就先访问右边
    PostMirrorOrder(root->left, v);//再访问左边，形成的是和正常地是一样的序列。
    v.push_back(root->value);
}

int main(){
    int n;
    Node* s = NULL;
    scanf("%d", &n);
    vector<int> num, pre, preM, post, postM;
    for(int i=0; i<n; i++){
        int data;
        scanf("%d", &data);
        num.push_back(data);
        Insert(s, data);//使用指针传递，第一次就不是null了.
        //此处建树最终建成的是一个标准的搜索二叉树。
    }
    PreOrder(s, pre);
    if(num == pre){//判断两个向量是否相等，直接判断就可以了。
        PostOrder(s, post);
        printf("YES
");
        for(unsigned int i=0; i<post.size(); i++){
            printf("%d", post[i]);
            if(i < post.size()-1) printf(" ");
        }
    }
    else{
        PreMirrorOrder(s, preM);
        if(num == preM){
            PostMirrorOrder(s, postM);
            printf("YES
");
            for(unsigned int i=0; i<postM.size(); i++){
                printf("%d", postM[i]);
                if(i < postM.size()-1) printf(" ");
            }
        }
        else printf("NO
");
    }
    return 0;
}

//这个感觉是正常地思路。

1.首先按输入序列，建成一个标准的二叉搜索树，并且保存输入序列为num（题目中给的也是前序遍历）。

2.然后对其进行前序遍历，得到结果pre;

3.此时将pre与输入序列对比，如果=，那么就是正常的二叉搜索树

4.否则就可能是镜像或者完全不是两者。

5.此时对二叉树进行镜像前序遍历（因为镜像也就是将左右子树反转，那么此时访问根节点后，再访问建好的二叉树的右子树不就相当于对镜像进行前序遍历了吗）

6.得到的结果是preM,如果和num相同那么就是镜像的，然后对其进行后序镜像遍历输出

7.否则不是二者，输出no.

//厉害，学习了，建树的过程，以及前序和后序遍历，都明白了，多复习！