39°

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。

//方案一:

public class Solution {

public boolean VerifySquenceOfBST(int [] sequence) {
int len=sequence.length-1;

if(len<0)
    return false;
int i=0;
while(len>0){
    while(sequence[i]<sequence[len])
        i++;
    while(sequence[i]>sequence[len])
        i++;
    
    if(i<len)
        return false;
    i=0;
    len--;
}

return true;

}

}

//方案二

public class Solution {

public boolean VerifySquenceOfBST(int [] sequence) {

int len=sequence.length-1; if(len<0) return false; return f(sequence,0,len); }

public boolean f(int a[],int start,int end){ if(start==end) return true;

int left=start;

while(a[left]&lt;a[end]&amp;&amp;left&lt;end)
    left++;

int right=left;

while(a[right]&gt;a[end]&amp;&amp;right&lt;end)
    right++;

if(right&lt;end)
    return false;

if(left==start||left==end)//只有左子树或者只有右子树
    return f(a,start,end-1);

else //既有左子树又有右子树
    return f(a,start,left-1)&amp;&amp;f(a,left,end-1);

}

}

//感觉似乎方案一更好理解,方案二思路上好像更简单些

本文由【南】发布于开源中国,原文链接:https://my.oschina.net/u/2511906/blog/3136585

全部评论: 0

    我有话说: