刷题17——面试题33：二叉搜索树的后续遍历序列

题目：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组任意两个数字都互不相同。例如，输入数组{5，7，6，9，11，10，8}，返回true，因为这个整数序列是下图二叉搜索树的后序遍历结果。如果输入的数组是{7，4，6，5}，则由于没有哪棵二叉搜索树的后续遍历结果是这个序列，因此返回false。

思路：

在后序遍历得到的序列中，最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大。

以数组{5，7，6，9，11，10，8}为例，后续遍历结果的最后一个数字8就是根节点的值。在这个数组中，前3个数字5、7和6都比8小，是值为8的节点的左子树节点；后3个数字9、11和10都比8大，是值为8的节点的右子树节点。

接下来用同样的方法确定与数组每一部分对应的子树的结构。这其实就是一个递归的过程。对于序列{5，7，6}，最后一个数字6是左子树的根节点的值。数字5比6小，是值为6的节点的左子节点，而7则是它的右子节点。同样，在序列{9，11，10}中，最后一个数字10是右子树的根节点，数字9比10小，是值为10的节点的左子节点，而11则是它的右子节点。

我们再来分析另一个整数数组{7，4，6，5}。后序遍历的最后一个数字是根节点，因此根节点的值是5.由于第个数字7比5大，因此在对应的二叉搜索树中，根节点上是没有左子树的，数字7、4和6都是右子树节点的值。但我们发现在右子树中有一个节点的值是4，比根节点的值5小，这违背了二叉搜索树的定义。因此，不存在一棵二叉搜索树，它的后续遍历结果是{7，4，6，5}。

python代码如下：

class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False
        
        #获取根节点
        root =sequence[-1]
        
        #根据二叉树性质，左孩子的每个节点的值都小于根节点
        for i in range(len(sequence)):
            if sequence[i]>root:
                break
            
        #判断是否右子树的每个节点的值都大于根节点
        for j in range(i, len(sequence)):
            if sequence[j] <root:
                return False
            
        left =True
        #i>0的时候证明有左孩子
        if i>0:
            #递归遍历左孩子
            left =self.VerifySquenceOfBST(sequence[:i])
            
        right =True
        #证明有右孩子，通过i的值不在最后一个节点进行判断
        if i<len(sequence)-1:
            right =self.VerifySquenceOfBST(sequence[i:-1])
            
        return left and right

java代码如下：

public boolean verifySquenceOfBST(int[] sequence){
    if(sequence ==null)
        return false;
    return verifyBST(squence, 0, squence.length-1);
}

private boolean verifyBST(int[] sequence, int start, int end){
    if(start>=end)
        return true;
    int root =sequence[end];    //后序遍历的最后一个节点为根节点
    //在二叉搜索树中左子树的节点小于根节点
    int i=0;
    for(;i<end;++i){
        if(sequence[i] >root)
            break;
    }
    //在二叉搜索树中右子树的节点大于根节点
    int j=i;
    for(;j<end;++j){
        if(sequence[j]<root)
            return false;
    }
    //判断左子树是不是二叉树
    boolean left =true;
    if(i>start){
        left =verifyBST(sequence, start, i-1);
    }
    //判断右子树是不是二叉树
    boolean right =true;
    if(i<end){
        right =verifyBST(sequence, i, end-1);
    }
    return (left && right);
}

更多精彩，关注“咋家”