剑指offer面试题系列

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

分析

拿到本题时，其实很快就想出了思路，就是在实现的过程中有几个细节问题没有注意到，导致调试了半天。这个在后面的备注里会提到。先说思路：

由于是后序遍历二叉树产生的序列，因为后序遍历的特点是最后遍历根节点，所以自然数组的最后一个元素就是根节点了。又因为是二叉排序树，所以根节点的左子树的全部元素是小于根节点的，相应的右子树全部大于根节点。根据这个性质，可以很容易在数组中划分出来哪部分是左子树，哪部分是右子树。只要从数组的第一个元素开始遍历，直到遍历到大于这个根节点的元素为止，前面的是左子树，后面的自然就是右子树了。

依次类推，使用递归可以实现之。

代码

    package com.tree;

/*判断输入数组是否是二叉搜索树的后序遍历序列
 * */
public class BinaryTreeEx {
    private static int[] arr1 = { 1, 2, 4, 3, 7, 9, 6, 8 };
    private static int[] arr2 = { 1, 3, 2 };
    private static int[] arr3 = { 3, 2, 5, 6, 4 };
    private static int[] arr = { 3, 2, 4, 1 };

    public static boolean isPostOrderSeq(int[] arr, int start, int end) {
        boolean flag = true;
        if (start >= end) { //先判断输入是否合适
            return flag;
        }
        int root = arr[end];
        int i = start;  //i从start开始遍历
        int pos = 0;
        while (i < arr.length && arr[i] < root)
            i++;
        pos = i;
        int right_len = end - pos;//左子树长度
        int left_len = pos - start;//右子树长度

        if (left_len > 0) {
            for (int k = start; k < left_len; k++) {
                if (arr[k] > root) {
                    flag = false;
                    break;
                }
            }

        }

        if (flag && right_len > 0) {
            for (int k = pos; k < end; k++) {
                if (arr[k] < root) {
                    flag = false;
                    break;
                }
            }

        }

        if (flag)
            flag = isPostOrderSeq(arr, start, pos - 1);
        if (flag)
            flag = isPostOrderSeq(arr, pos, end - 1);
        return flag;
    }

    public static void main(String[] args) {
        if (isPostOrderSeq(arr, 0, arr.length - 1))
            System.out.println("该序列是后序遍历序列");
        else
            System.out.println("该序列不是后序遍历序列");
    }
}

备注

有两个地方需要注意：

第一，是每次递归划分左右子树的变量 i 的起点，因为每次将 i=0，在调试时费了不少功夫；而计算左右子树的表达式也要注意；

第二，在递归右子树时，记得输入参数的时候将 end 变量减去 1，因为每次都把最后一个结点踢出来了。

总结

前面很多题是思路没有想清楚，实现没啥问题；这个题是思路没有想清楚，实现的细节上费了很大功夫。以后做题，思路先要想清楚，然后在细节上，特别是一些变量的设置上要注意。