剑指offer - 二叉搜索树的后序遍历序列

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是返回true，否则返回false。

假设输入的数组的任意两个数字互不认识。例如，输入数组{5,7,6,9,11,10,8}，则返回true，因为这个整数序列是图4.9二叉树的后序遍历结果。如果输入的数组是{7，4，6，5}，则由于没有哪棵二叉树的后序遍历结果是这个序列，因此返回false

1.jpeg

思路

在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：

• 第一部分是左子树结点的值，它们都比根结点的值小
• 第二部分是右子树的值，它们都比根结点的值大

充分利用这个特性我们就能解决问题

分析

以数组{5,7,6,9,11,10,8}为例，后序遍历结果的最后一个数字8就是根结点的值。数组中，前面3个数字5，7，6都比8小，所以它们是左子树的结点，后3个数字9，11，10都比8大，因而是右子树的结点

使用相同的规则来确定数组中每一部分对应的子树的结构，显然就是递归。对于序列{5,7,6}，最后一个数组6是左子树根结点的值。数字5比6小，是值为6的结点的左子结点，而7则是它的右子结点。同样，{9,11,10}，10为右子树的根结点，9比10小，所以是值为10的左子结点，而11比10大，是值为10结点的右子结点。

算法实现

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++) {
        if (sequence[i] > root)
            break;
    }

    // 二叉搜索树中右子树结点的值大于根结点的值
    int j = i;
    for (; j < length - 1; j++) {
        if (sequence[j] < root)
            return false;
    }

    // 判断左子树是不是二叉搜索树
    bool left = true;
    if (i > 0)
        left = VerifySquenceOfBST(sequence, i);

    // 判断右子树是不是二叉搜索树
    bool right = true;
    if (i < length - 1)
        right = VerifySquenceOfBST(sequence + i,length - i - 1);

    return (length && right);
}

非递归

非递归也是一个基于递归的思想：

左子树一定比右子树小，因此去掉根结点后，数字分为left，right两部分。right部分的，最后一个数字是右子树的根他也比左子树所有值大，因此我们可以每次只看右子树是否符合条件即可，即使到达了左子树左子树也可以看出由左右子树组成的树还是像右子树那样处理

bool VerifySquenceOfBST2(vector<int> sequence) {
        unsigned long size = sequence.size();
        if(0 == size) return false;

        int i = 0;
        while(--size)
        {
            while(sequence[i++]<sequence[size]);
            while(sequence[i++]>sequence[size]);

            if(i<size)return false;
            i=0;
        }
        return true;
}

参考

《剑指offer》
二叉搜索树的后序遍历序列