剑指offer_面试题24_二叉搜索树的后序遍历序列（递归）

「爱情、让人受尽委屈。」 2022-08-04 04:15 113阅读 0赞

**题目：**输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

**二叉搜索树规律：**

1、若 左子树 不空，则 **左子树**上所有结点的值 **均小于**它的根结点的值。

2、若 右子树 不空，则 **右子树**上所有结点的值 **均大于**它的根结点的值。

3、左右子树也分别为二叉搜索树。

**举例1：**

输入数组：\{5、7、6、9、11、10、8\}

后序遍历规律：左 - 右 - 根

5小于8====》5、7、6 左子树 ===判断是否都小于8====》是 ====递归====》5 左子树；7 右子树；6 根 ======》符合

9大于8====》9、11、10 右子树 ===判断是否都大于8====》是====递归=====》9 左子树；11 右子树；10 根======》符合

====》8 根

**举例2：**

输入数组：\{7，4，6，5\}

====》5 根

====》7大于5，因此 7、4、6 ====》属于右子树 ===判断是否都大于5==》否===》说明不是 二叉搜索树后序遍历序列

**算法如下：**

bool VerifySquenceofBST(int a[],int length)
    {
        if(NULL == a || length <= 0)
            return false;
    
        int pRoot = length - 1;
    
    /**二叉搜索树的四个规律*/
        /**1、在二叉搜索树中左子树的结点小于于根结点*/
        int i = 0;
        while(i < length - 1)
        {
            if(a[i] > a[pRoot])
                break;
            i++;
        }
    
        /**2、在二叉搜索树中右子树的结点大于根结点*/
        int j = i;
        while(j < length - 1)
        {
            if(a[j] < a[pRoot])
                return false;
            j++;
        }
    
        /**3、判断左子树是不是二叉搜索树*/
        bool left = true;
        if(i > 0)
            left = VerifySquenceofBST(a, i);
    
        /**4、判断右子树是不是二叉搜索树*/
        bool rigth = true;
        if(i < length - 1)
            rigth = VerifySquenceofBST(a + i, length - i - 1);
    
        return (left && rigth);
    }

**总结：**

**举实例分析，有助理解**

**算法 与 规律 相对应，分析过程，总结规律。**

/\* 点滴积累，我的一小步 \*/