关于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);
}