一、题目内容

image.png

二、题解

解法1：

思路

image.png

代码

  1. class Solution {
  2.     public boolean verifyPostorder(int[] postorder) {
  3.         return recur(postorder,0,postorder.length - 1);
  4.     }
  6.     public boolean recur(int[] postorder, int left, int right){
  7.         if(left >= right){
  8.             return true;
  9.         }
  10.         int rightFirst = left;
  11.         while(postorder[rightFirst] < postorder[right]) {
  12.             rightFirst++;
  13.         }
  14.         int rightFirstCopy = rightFirst;
  15.         //找到第一个不大于根节点的节点，看是否为根节点
  16.         while(postorder[rightFirst] > postorder[right]) {
  17.             rightFirst++;
  18.         }
  19.         boolean verifyCurrent = rightFirst == right;
  20.         boolean isLeftVerify = recur(postorder,left, rightFirstCopy-1);
  21.         boolean isRightVerify = recur(postorder,rightFirstCopy,right-1);
  22.         return  verifyCurrent && isLeftVerify && isRightVerify;
  23.     }
  24. }