// 面试题33：二叉搜索树的后序遍历序列// 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。// 如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。#include 
     
      // BST：Binary Search Tree，二叉搜索树bool VerifySquenceOfBST(int sequence[], int length){    if (sequence == nullptr || length <= 0)//先看错误输入        return false;    int root = sequence[length - 1];//后续遍历的最后一个是根节点    // 在二叉搜索树中左子树的结点小于根结点    int i = 0;//设成非循环变量    for (; i < length - 1; ++i)//先加后判断，所以得到的i不是下标，是长度    {        if (sequence[i] > root)            break;    }    // 在二叉搜索树中右子树的结点大于根结点    int j = i;//这里用到i，所以上述i不拿到循环里    for (; j < length - 1; ++j)//只检测右子树有没有小于根节点的，有就不满足二叉搜索树的性质    {        if (sequence[j] < root)            return false;    }    // 判断左子树是不是二叉搜索树    bool left = true;    if (i > 0)//结合上条初始化为true，这里就能限制左子树为空子树的情况        left = VerifySquenceOfBST(sequence, i);    // 判断右子树是不是二叉搜索树    bool right = true;    if (i < length - 1)//同上        right = VerifySquenceOfBST(sequence + i, length - i - 1);    return (left && right);}// ====================测试代码====================void Test(const char* testName, int sequence[], int length, bool expected){    if (testName != nullptr)        printf("%s begins: ", testName);    if (VerifySquenceOfBST(sequence, length) == expected)        printf("passed.\n");    else        printf("failed.\n");}//            10//         /      \//        6        14//       /\        /\//      4  8     12  16void Test1(){    int data[] = { 4, 8, 6, 12, 16, 14, 10 };    Test("Test1", data, sizeof(data) / sizeof(int), true);}//           5//          / \//         4   7//            ///           6void Test2(){    int data[] = { 4, 6, 7, 5 };    Test("Test2", data, sizeof(data) / sizeof(int), true);}//               5//              ///             4//            ///           3//          ///         2//        ///       1void Test3(){    int data[] = { 1, 2, 3, 4, 5 };    Test("Test3", data, sizeof(data) / sizeof(int), true);}// 1//  \//   2//    \//     3//      \//       4//        \//         5void Test4(){    int data[] = { 5, 4, 3, 2, 1 };    Test("Test4", data, sizeof(data) / sizeof(int), true);}// 树中只有1个结点void Test5(){    int data[] = { 5 };    Test("Test5", data, sizeof(data) / sizeof(int), true);}void Test6(){    int data[] = { 7, 4, 6, 5 };    Test("Test6", data, sizeof(data) / sizeof(int), false);}void Test7(){    int data[] = { 4, 6, 12, 8, 16, 14, 10 };    Test("Test7", data, sizeof(data) / sizeof(int), false);}void Test8(){    Test("Test8", nullptr, 0, false);}int main(int argc, char* argv[]){    Test1();    Test2();    Test3();    Test4();    Test5();    Test6();    Test7();    Test8();    system("pause");    return 0;}