Zhao70's Blog

PAT1043. Is It a Binary Search Tree

发表于 | 分类于

题目大意

1043. Is It a Binary Search Tree
注意此处的二叉搜索树定义

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.

PS: 没认真读题还去找强哥问, 真是切腹自尽算了…

给定前序遍历, 问是一棵BST还是镜像BST, 是的话, 则输出YES, 以及后序遍历, 否则, 输出NO.

题目分析

最开始写了四个函数(判断是否BST, 判断是否镜像BST, 求BST的后序, 求镜像BST的后序). 后来看了柳婼的code, 发现只需要一个函数. 直接求后序, 然后一个全局变量标记是否为镜像, 进行不同的判断. 如果不是BST的话, 则不会遍历所有结点(return 会提前返回), 因此长度不足n. 同理可以判断是否为镜像BST.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
using namespace std;
vector<int> preOrder;
vector<int> postOrder;
bool isMirror = false;
int nNode;
void prPostOrder(){
    cout << "YES" << endl;
    for(int i = 0; i < nNode; i++){
        if(i != 0)
            cout << " ";
        cout << postOrder[i];
    }
}
void bst(int begin, int end){
    if(end < begin)
        return;
    if(begin == end){
        postOrder.push_back(preOrder[begin]);
        return;
    }
    int rootKey = preOrder[begin];
	//注意此处i, j的含义 以及 初始值
    int i = end;
    int j = begin + 1;
    if(isMirror == false){
        while(i >= begin + 1 && preOrder[i] >= rootKey)
            --i;
        while(j <= end && preOrder[j] < rootKey)
            ++j;
    }
    else{
        while(i >= begin + 1 && preOrder[i] < rootKey)
            --i;
        while(j <= end && preOrder[j] >= rootKey)
            ++j;
    }
    if(i > j)
        return;
    bst(begin + 1, i);
    bst(j, end);
    postOrder.push_back(rootKey);
}
int main(){
    cin >> nNode;
    for(int i = 0; i < nNode; i++){
        int key;
        cin >> key;
        preOrder.push_back(key);
    }
    bst(0, nNode - 1);
    if(postOrder.size() != nNode){
        isMirror = true;
        postOrder.clear();
        postOrder.resize(0);
        bst(0, nNode - 1);
    }
    if(postOrder.size() == nNode)
        prPostOrder();
    else
        cout << "NO";
    return 0;
}