剑指33 二叉搜索树的后序遍历序列

  1. class Solution {
  2.     public boolean verifyPostorder(int[] postorder) {
  3.         if(postorder == null) 
  4.             return false;
  6.         if(postorder.length == 0)
  7.             return true;
  9.         return verifyPostorderBST(postorder, 0, postorder.length - 1);    
  11.     }
  13.     private boolean verifyPostorderBST(int[] postorder, int left, int right) {
  14.         if (left >= right)
  15.             return true;
  17.         int root = postorder[right];
  18.         int i = left;
  19.         for (i = left; i < right; i++)
  20.             if (postorder[i] > root)
  21.                 break;
  23.         int j = i;
  24.         for (j = i; j < right; j++) 
  25.             if (postorder[j] < root)
  26.                 return false;
  28.         boolean l = true;
  29.         if (i > 0)
  30.             l = verifyPostorderBST(postorder, left, i - 1);
  32.         boolean r = true;
  33.         if (i < right)
  34.             r = verifyPostorderBST(postorder, i, right - 1);
  36.         return (l && r);
  37.     }
  38. }