3. 二叉查找树的后序遍历

1. 3. 二叉查找树的后序遍历

【问题描述】输入一个整数数组，判断该数组是不是某二叉查找树的后序遍历的结果。如果是返回true，否则返回false。
【输入形式】输入任意长度的数组，数字之间空格分开
【输出形式】true 或者 false
【样例输入】输入5 7 6 9 11 10 8
【样例输出】true
【样例说明】由于这一整数序列是如下树的后序遍历结果：

          8
       /      \
      6      10
    /   \     /   \
   5   7   9  11

因此返回true。

【评分标准】暴力求解法不得分。

【提示】后序遍历的最后一个结点一定是根结点，那么前面的数据就可以划分为比根小的、比根大的。依此类推下去。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// 对于一个二叉树的后序遍历序列来说，最后一个数一定是根节点，
// 然后前面的数中，从最开始到第一个大于根节点的数都是左子树中的数，
// 而后面到倒数第二个数应该都是大于根节点的，
// 是右子树，如果后面的数中有小于根节点的，
// 那么说明这个序列不是二叉搜索树的后序遍历序列。
bool Islast(vector<int> a)
{
    vector<int> v1, v2;
    int i;
    for (i = 0; i < a.size() - 1; i++)
    {
        if (a[i] < a[a.size() - 1])
        {
            v1.push_back(a[i]);
        }
        else
            break;
    }
    for (int j = i; j < a.size() - 1; j++)
    {
        if (a[j] > a[a.size() - 1])
        {
            v2.push_back(a[j]);
        }
        else
            return false;
    }
    bool l = true, r = true;
    if (!v1.empty())
        l = Islast(v1);
    if (!v2.empty())
        r = Islast(v2);
    return l && r;
}
int main()
{
    int data;
    vector<int> a;
    while (cin >> data)
    {
        if (data != 0)
        {
            a.push_back(data);
        }
        else
            break;
    }
    if (Islast(a))
        cout << "true";
    else
        cout << "false";
}