04-树7. Search in a Binary Search Tree

Posted on   |   In   |  

To search a key in a binary search tree, we start from the root and move all the way down, choosing branches according to the comparison results of the keys. The searching path corresponds to a sequence of keys. For example, following {1, 4, 2, 3} we can find 3 from a binary search tree with 1 as its root. But {2, 4, 1, 3} is not such a path since 1 is in the right subtree of the root 2, which breaks the rule for a binary search tree. Now given a sequence of keys, you are supposed to tell whether or not it indeed correspnds to a searching path in a binary search tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (<=100) which are the total number of sequences, and the size of each sequence, respectively. Then N lines follow, each gives a sequence of keys. It is assumed that the keys are numbered from 1 to M.

Output Specification:

For each sequence, print in a line “YES” if the sequence does correspnd to a searching path in a binary search tree, or “NO” if not.

1
2
3
4
5
6
7
8
9
Sample Input:
3 4
1 4 2 3
2 4 1 3
3 2 4 1
Sample Output:
YES
NO
NO

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<vector>
using namespace std;

bool Compute(vector<int> &ivec, int position, bool flag)
{
    for(int i = position + 2; i < ivec.size(); ++i)
    {
        if(flag)        //if flag is true, all element should greater than vector[position]
        {
            if(ivec[i] <= ivec[position])
            {
                return false;
            }
        }
        else    //if flag is false, all element should less than vector[position]
        {
            if(ivec[i] >= ivec[position])
            {
                return false;
            }
        }
    }
    return true;
}
bool Check(vector<int> &ivec)
{
    if(ivec.size() < 3)
    {
        return true;
    }
    for(int j = 1; j < ivec.size(); ++j)
    {
        if(ivec[j] > ivec[j-1])
        {
            if(!Compute(ivec, j-1, true))
            {
                return false;
            }
        }
        else if(ivec[j] < ivec[j-1])
        {
            if(!Compute(ivec, j-1, false))
            {
                return false;
            }
        }
        else        //if they are equal ,return false
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int N = 0, M = 0;//N is number of test cases, M is size of each sequence
    cin >> N >> M;
    for(int i = 0; i < N; ++i)
    {
        int val = 0;
        vector<int> ivec;
        for(int j = 0; j < M; ++j)
        {
            cin >> val;
            ivec.push_back(val);
        }
        if(Check(ivec))
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }

    return 0;
}

又是一个一遍就AC的代码，不过写的不好，时间复杂度非常高。
思路：
因为是二叉搜索树，必定遵循的原则就是：右>根>左。
举例来说：序列：

1
1 4 2 3

4 > 1,意味着4是右子树，同时也意味着4后面所有的元素都是右子树中的元素（注意题目说了这是搜索路径），这就说明4后面的所有元素都要大于1才正确，同理类推，2<4，所以2是4的左子树，2后面所有的元素都要小于4才正确。依次类推，全部符合要求即输出YES，否则输出NO。