从零学算法（剑指 Offer 33）

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

     5
    / \
   2   6
  / \
 1   3
1
2
3
4
5

示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true

• 我的思路：二叉搜索树就是左节点都小于根节点，右节点都大于根节点，子树同样满足该条件。那么不难想到，递归部分就是不断分出一棵棵子树判断是否符合左小右大的特点。入参当然就是代表一棵子树的数组的起止下标。由于是后序遍历，所以右边界就是根节点。如果右边界（下标）小于左边界（下标）那说明子树都判断完了，竟然在这之前都没返回 false 那只能返回 true 了。然后定义一个下标从右边界开始往前找，如果有比根节点小的，说明从右子树找到了左子树了，此时的下标就是左子树的右边界，遍历的过程其实相当于把右子树都找完了，继续往前遍历这个下标，等于遍历左子树，判断是否都小于根节点即可，然后继续判断划分出的左右子树

•   int[] pos;
    public boolean verifyPostorder(int[] postorder) {
        this.pos=postorder;
        return dfs(0,pos.length-1);
    }
    // root 也可以理解为 right，因为是后序遍历数组
    public boolean dfs(int left,int root){
        if(root < left)return true;
        // 找到第一个小于根节点的下标，这就是左子树的右边界
        int firsetLess = root-1;
        while(firsetLess >=0 && pos[firsetLess]>pos[root]){
            firsetLess--;
        }
        // 遍历左子树
        for(int i = firsetLess;i>=0;i--){
            if(pos[i]>pos[root])return false;
        }
        return dfs(firsetLess+1,root-1) && dfs(left,firsetLess);
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• 他人题解1：思路一样，不过代码实现更巧妙一些，他是从前往后找，先默认左子树都正确，然后判断没有直接判断右子树的每个值是否都大于根节点，而是只要大于根节点就往后遍历，让他遍历到根节点为止，如果能够到达根节点，说明的确是都大于根节点，否则自然是有问题了。用最后的下标是否等于根节点来转换了右子树正确性的问题。

•   public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        // 划分左子树
        while(postorder[p] < postorder[j]) p++;
        // m，p 为右子树起点 
        int m = p;
        // 只要右子树合法 p 最终就会遍历到根节点，然后 postorder[p] == postorder[j]) 就结束循环了
        while(postorder[p] > postorder[j]) p++;
        // 所以最终结果就是 p 是否等于 j 以及递归进行左右子树的判断
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

• 他人题解2：还有一种我似懂非懂的解法，把后序遍历倒序，你会得到根右左的数组，这时遍历该数组，你会先得到一个递增的数组，然后，只要发现有递减的数了，说明到了左子树，那么左子树应该满足所有数都小于根节点。根节点怎么找呢，你会发现，根节点有个特性，根节点一定是大于左节点且最接近左节点的数，比如后序数组为 132，倒序后为 231，之前的 23 都好好的，是升序的，遍历到 1 时说明到左子树了，根节点肯定在前面，所以需要用一个数据结构来存储前面的 23，2 是根，需要使用到它，3 不是根并且由于之后要判断的所有数只要小于根就行，所以之后也用不到它了，需要移除，那么能够满足我们需求的就是使用栈，存储时为 23，遍历时弹出 3 然后弹出 2，此时根节点为 2，之后遍历的数都应该小于 2

•   public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        // 初始根节点是没有根节点的，所以为了最开始是符合条件的
        // 那么我们就用一定符合条件的最大值默认为他的根节点
        // 因为我们是根据判断左子树来验证是否为搜索树
        // 所以也就等同于我们默认根节点为一个节点的左节点，那这个结点自然是要一个一定大于根节点的数
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
        	// 若当前数大于根节点就有问题了
            if(postorder[i] > root) return false;
            // 只要突然递减了就会进入循环寻找根节点 root
            // 找到找完或者存储的数小于当前节点为止
            // 这也就代表我们找到了最接近当前节点的值并且大于这个值的节点
            // 也就是根节点
            // 也是由于整体趋势是根右左，大体呈现为降序
            // 所以我们顺序遍历的整体趋势也同样是从大往小遍历
            // 所以在验证的过程中 root 也是越来越小的
            while(!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            // 把点都 push 进去，以备之后寻找 root
            stack.add(postorder[i]);
        }
        return true;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24

• 建议还是看原文的讲解，我唯一不理解的点就在于左节点永远不是和它的直接根节点比较，而是和爷节点比较，这是怎么验证正确性的