33. 二叉搜寻树的后序遍历序列
思路：
-
搜寻树的后果的特点
- 头节点左侧的数比头节点小；右侧的数比头节点大。
- 数组后果的最初一位是树的头节点
所以能够按头节点分为左右子树后，是否分完，再判断分进去的左右子树是否能被它们的头节点分来源gao*daima.com搞@代#码网成正好右边都小，左边都大。
代码：
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);
}
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：关于java:33-二叉搜索树的后序遍历序列
转载请注明原文链接：关于java:33-二叉搜索树的后序遍历序列
