Description

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

参考以下这颗二叉搜索树：

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

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

提示：

  1. 数组长度 <= 1000

Solution

后序遍历的特点是：左子树 | 右子树 | root
root 节点一定在当前子树遍历序列的最后一位，而右子树中所有的值都必须是大于 root，左子树中的所有值都需要小于 root。
判断某数组是不是某二叉搜索树的后序遍历结果的必要条件是：左子树必须小于 root 节点，右子树必须大于 root 节点。
所以结合上述方式，算法的执行流程如下：

递归算法的执行过程：

  1. 获取当前 root 节点，root 节点位于遍历序列的最后一位
  2. 获取左子树 root 节点，从当前子树的遍历序列的起始开始遍历，遇到第一个大于 root 节点的值的时候，即找到左子树和右子树的分界点，往后退一格就是左子树的 root 节点。 因为左子树的所有值都小于当前子树 root 节点，并且左子树的 root 节点一定位于左子树的遍历序列的最后一位。
  3. 判断右子树中的所有值是否大于 root 节点的值
  4. 递归判断左右子树是否满足条件

以 [1,3,2,6,5] 为例：
当前子树的 root 节点为 5， 左子树为 [1,3, 2]， 右子树为 [6]

  1. class Solution {
  2.     public boolean verifyPostorder(int[] postorder) {
  3.         return verifyPostorder(postorder, 0, postorder.length-1);
  4.     }
  5.     public boolean verifyPostorder(int[] postorder,int lo, int hi) {
  6.         if (lo >= hi){
  7.             return true;
  8.         }
  9.         int root = postorder[hi];
  10.         int leftRoot = lo;
  11.         int i = lo;
  12.         for (; i < hi; i ++){
  13.             if (postorder[i] > root){
  14.                 leftRoot = i - 1;
  15.                 break;
  16.             }
  17.         }
  18.          // 检查右子树是否存在小于 root 的值
  19.         for (; i < hi; i ++){
  20.             if (postorder[i] < root) {
  21.                 return false;
  22.             }
  23.         }   
  24.         return verifyPostorder(postorder, lo, leftRoot) && verifyPostorder(postorder, leftRoot + 1, hi-1);
  25.     }  
  26. }