[剑指Offer]-二叉搜索树的后序遍历

题目描述

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

回顾后序遍历的特点我们可以直到数组的最后一位一定时根节点。而二叉搜索树是一种空树或者二叉树的所有结点比它的左子结点大，比它的右子结点小。

后序遍历：5， 7， 6， 9， 11， 10， 8

解题思路

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

• 以数组{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的左子结点，7是根结点6的右子结点；同样对于序列9， 11， 10的子树而言，10是根结点，9是根结点10的左子结点，11是根结点10的右子结点。

• 以数组{7， 4， 6， 5}为例，后序遍历的结果中最后一个值5就是根结点。数组的第一个数字7大于5，故此二叉搜索树没有左子树， 7， 4， 6都是右子树结点的值。我们发现4比5小，违背了二叉搜索树的规定。故此数组不是二叉搜索树的后序遍历。

算法图解

参考代码：

package offer;

/**
 * 二叉搜索树的后序遍历
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 * 5    7   6   9   11  10  8   8为根
 */
public class Offer33 {
    public static void main(String[] args) {
        int nums[] = {5, 7, 6, 9, 11, 10, 8};
        int nums2[]={7,4,6,5};
        System.out.println(VerifySquenceOfBST(nums,0, nums.length));
        System.out.println(VerifySquenceOfBST(nums2,0, nums2.length));
    }

    private static boolean VerifySquenceOfBST(int nums[],int start , int length) {
        if (nums == null || length <= 0) {
            return false;
        }
        int root = nums[length-1];
        int index;
        for (index = 0; index < length-1 ; index++) {
            if (nums[index] > root) {
                break;
            }
        }
        // 在小值后面如果还出现了小值 肯定不是搜索树
        int index2=index;
        for (; index2 < length -1; index2++) {
            if (nums[index2] < root) {
              return false;
            }
        }
        // 找到两个分界点  在递归判断  二分查找

        boolean left = true;
        if (index > 0) {
            left = VerifySquenceOfBST(nums,0, index);
        }
        boolean right = true;
        if (index2 < length-1 ) {

            right = VerifySquenceOfBST(nums,index, index2);
        }
        return  right;
    }
}

附录

该题源码在我的 ????Github 上面！