关于java:33-二叉搜索树的后序遍历序列

33. 二叉搜寻树的后序遍历序列

思路：

• 搜寻树的后果的特点

  • 头节点左侧的数比头节点小；右侧的数比头节点大。
  • 数组后果的最初一位是树的头节点

  所以能够按头节点分为左右子树后，是否分完，再判断分进去的左右子树是否能被它们的头节点分成正好右边都小，左边都大。

代码：

public boolean verifyPostorder(int[] postorder) {    if (postorder.length<1) return true;    ArrayList<Integer> a = new ArrayList<>();    for (int i = 0; i < postorder.length; i++) {        a.add(postorder[i]);    }    return verify(a);}public boolean verify(ArrayList<Integer> postorder){    if (postorder.size()<=1) return true;    int mid = postorder.get(postorder.size()-1);    int i = 0;    ArrayList<Integer> left = new ArrayList<>();    ArrayList<Integer> right = new ArrayList<>();    while(postorder.get(i)<mid){        left.add(postorder.get(i++));        if (i==postorder.size()) break;    }    while(postorder.get(i)>mid){        right.add(postorder.get(i++));        if(i==postorder.size()) break;    }    if (i < postorder.size()-1) return false;    return verify(left) && verify(right);}