判断数组是否是二叉树搜索树的后序遍历结果

思路:判断是否能根据数组成功重建二叉树

重要的点,后序遍历即最后一个数字是根节点

代码:

简单粗暴方法
主要目标是找到左子树结束的点,因为有可能没有左子树,因此这里先将左子树开始的点设置为左边界之前的一个点;

  public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence==null||sequence.length<1){
            return false;
        }
        if (sequence.length==1){
            return true;
        }

        //每个子数组中最后一个元素为根节点,找到第一个大于根节点的位置，则该位置左边为左子树，右边为右子树；
        return checkArr(sequence,0,sequence.length-1);
    }

    private boolean checkArr(int[] sequence, int startIndex, int endIndex) {
        if (startIndex>=endIndex){
            return true;
        }

        //最后一个数字为根
        int rootNum=sequence[endIndex];

        //找到左子树结束的点
        int leftEndIndex=startIndex-1;

        for (int i = startIndex; i <endIndex ; i++) {
            if (sequence[i]<rootNum){
                leftEndIndex++;
            }else {
                break;
            }
        }

        //左子树的节点值都应该小于根======>>>>>>>>>>>>>>>>>这一步其实可以省略,因为上一个for循环已经确定了leftEndIndex前的都小于根
        for (int i = startIndex; i <=leftEndIndex ; i++) {
            if (sequence[i]>rootNum){
                return false;
            }
        }

        //右子树的节点值都应该大于根
        for (int i = leftEndIndex+1; i <=endIndex-1 ; i++) {
            if (sequence[i]<rootNum){
                return false;
            }
        }

        return checkArr(sequence,startIndex,leftEndIndex)&&checkArr(sequence,leftEndIndex+1,endIndex-1);
    }

上面代码里搞两个循环把左右子树合规性都判断了一次实际上欠考虑了,其实左子树不需要重新循环判断是否小于根了,我在找左子树结束节点的步骤已经确定了leftEndIndex前的都小于根

以下是更正后代码

  /**
     * 思路:判断是否能根据数组成功重建二叉树
     */
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence==null||sequence.length<1){
            return false;
        }
        if (sequence.length==1){
            return true;
        }

        //每个子数组中最后一个元素为根节点,找到第一个大于根节点的位置，则该位置左边为左子树，右边为右子树；
        return checkArr(sequence,0,sequence.length-1);
    }

    private boolean checkArr(int[] sequence, int startIndex, int endIndex) {
        if (startIndex>=endIndex){
            return true;
        }

        //最后一个数字为根
        int rootNum=sequence[endIndex];

        //找到左子树结束的点
        int leftEndIndex=startIndex-1;

        for (int i = startIndex; i <endIndex ; i++) {
            if (sequence[i]<rootNum){
                leftEndIndex++;
            }else {
                break;
            }
        }

        //右子树的节点值都应该大于根
        for (int i = leftEndIndex+1; i <=endIndex-1 ; i++) {
            if (sequence[i]<rootNum){
                return false;
            }
        }

        return checkArr(sequence,startIndex,leftEndIndex)&&checkArr(sequence,leftEndIndex+1,endIndex-1);
    }

```