PAT 解题报告 1043. Is It a Binary Search Tree (25)

1043. Is It a Binary Search Tree 题目描述:

题目要求根据给出的先序遍历判断对应的树是不是一个Binary Search Tree (BST), 或者Binary Search Tree (BST)的一个镜像(Mirror)的先序遍历. 如果是, 还要输出这棵树的后序遍历. 具体描述如下:

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.

1043. Is It a Binary Search Tree 算法分析:

算法分析倒是不难, 就是根据先序遍历+BST的性质进行构造这个BST, 或者试着构造出BST的镜像, 如果可以构造出也就是还原出这棵树的话, 那么这个先序就是一个合法的BST(or BST mirror)的一个先序序列. 然后根据构造的树, 进行一次后序遍历输出即可. 构造的过程是这样的: 因为给出的序列A[0, …, N-1]是先序, 那么A[0]一定是根, A[0]后面显示左子树(有可能是空)再是右子树, 那么就找到那个分割左右子树的点, 找这个点的同时进行判断条件: 左子树所有的节点都比A[0]小, 右子树所有的节点都比A[0]大, 如果是镜像的话就相反的判断. 最后过了所有的判断能够构造出这样的树的话, 我们再后序遍历输出. 有些实现细节要注意, 算法本身也不是特别难想到, 可以AC的代码如下:

#include <iostream>
#include <sstream>

#include <cstring>
#include <cstdio>
#include <cmath>

#include <algorithm>
#include <string>
#include <vector>

#define REP(i,n) for(int i=0;i<(n);++i)

using namespace std;

struct Node {
    int val;
    Node *left;
    Node *right;
};

bool flag;
int N;
int ele[1008];
Node *tree;

void init(Node *t) {
    t->val = 0;
    t->left = NULL;
    t->right = NULL;
}

Node *build(int l, int r) {
    if(l > r) return NULL;

    Node *root = new Node;
    init(root);
    root->val = ele[l];

    if(l == r) return root;

    int mid = l+1;
    for(int i=l+1; i<=r; ++i) {
        if(ele[i] >= ele[l]) {
            mid = i;
            break;
        }
        mid++;
    }
    for(int i=mid; i<=r; ++i) {
        if(ele[i]<ele[l]) {
            flag = false;
            return NULL;
        }
    }
    root->left = build(l+1, mid-1);
    root->right = build(mid, r);

    return root;
}

//mirror
Node *build2(int l, int r) {
    if(l > r) return NULL;

    Node *root = new Node;
    init(root);
    root->val = ele[l];
    if(l == r) return root;

    int mid = l+1;
    for(int i=l+1; i<=r; ++i) {
        if(ele[i] < ele[l]) {
            mid = i;
            break;
        }
        mid++;
    }
    for(int i=mid; i<=r; ++i) {
        if(ele[i] >= ele[l]) {
            flag = false;
            return NULL;
        }
    }
    root->left = build2(l+1, mid-1);
    root->right = build2(mid, r);

    return root;
}

ostringstream oss;

void dfs(Node *r) {
    if(NULL == r) return ;
    dfs(r->left);
    dfs(r->right);
    oss<<' '<<r->val;
}

void gao() {
    if(0 == N) return;
    if(1 == N) {
        cout<<"YES"<<endl;
        cout<<ele[0]<<endl;
        return;
    }

    flag = true;
    tree = new Node;
    init(tree);
    tree = build(0, N-1);
    if(flag) {
        cout<<"YES"<<endl;
        dfs(tree);
        cout<<oss.str().substr(1)<<endl;
        return ;
    }
    flag = true;
    tree = new Node;

    init(tree);
    tree = build2(0, N-1);

    if(flag) {
        cout<<"YES"<<endl;
        dfs(tree);
        cout<<oss.str().substr(1)<<endl;
        return ;
    }
    cout<<"NO"<<endl;
    return ;
}

int main(void) {
    cin>>N;
    REP(i, N) cin>>ele[i];
    gao();
    return 0;
}

1043. Is It a Binary Search Tree  注意点:

构造还原树的一些细节要注意, 比如空子树之类的, 详见代码.

 

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on January 18, 2014