第二十三题 二叉搜索树的后序遍历序列

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

分析

结合图中分析：

• 一棵 BST ：左孩子 < 根结点 < 右孩子
  
• 一棵 BST 的左子树或者右子树都是 BST
  

后序遍历是，左右根：[3, 4, 9, 5, 12, 11, 10]，结合图再从左往右分析后序序列，分析子树，可以发现：

• [3, 4, 9, 5] 10 [12, 11]
  • [3, 4] 5 [9]
    • [3] 4
  • [12] 11

发现对于每一棵子树，它的根结点总是对应该子树的后序序列的最后一个数
那么，只需要不断地确定出左子树区间和右子树区间，并且判断：左子树区间的所有结点值 < 根结点值 < 右子树区间所有结点值，这个条件是否满足即可

代码一:错误

 public static boolean VerifySquenceOfBST(int [] sequence) {
       if (sequence == null || sequence.length == 0) {
           return false;
       }
       return BST(sequence, 0, sequence.length-1);
    }
   public static boolean BST(int [] sequence,int start,int end) {
       if(start>=end)return true;
       int temp = sequence[end];
       int split = start;
       //这里的for循环有错误,原因是当数组是4675的时候,会出现右子树的根节点小于temp,
       //第一个for的split没有加一,从而导致第二个for循环的ifn判断为false;
       for(int i = start;i<end;i++)
       {
           if(sequence[i]>temp)
           {
               split = i;
               break;
           }
       }
       for(int j = split;j<end;j++)
       {
           if(sequence[j]<temp)
           {
               return false;
           }
       }
       return BST(sequence,start,split-1)&&BST(sequence, split, end-1);        
    }

代码二

public boolean VerifySquenceOfBST(int [] sequence) {
       if (sequence == null || sequence.length == 0) {
           return false;
       }
       return BST(sequence, 0, sequence.length-1);
    }
   public boolean BST(int [] sequence,int start,int end) {
       if(start>=end)return true;
       int temp = sequence[end];
       int split = start;
       for (; split < end && sequence[split] < temp; split++) ;
       for(int j = split;j<end;j++)
       {
           if(sequence[j]<temp)
           {
               return false;
           }
       }
       return BST(sequence,start,split-1)&&BST(sequence, split, end-1);        
    }