題目:
輸入一個(gè)整數(shù)數(shù)組果录，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果倡缠。如果是則輸出是的泡挺，否則輸出號(hào)假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
思路:
后序遍歷的結(jié)果最后一個(gè)元素是根元素,比根元素大的是右子樹(shù)序列,小的是左子樹(shù)序列.我們根據(jù)這個(gè)特性就可以通過(guò)遞歸解決這個(gè)問(wèn)題.
代碼
/**
* Created by Hammy on 2018/1/31.
*/
public class VerifySquenceOfBST
{
public boolean VerifySquenceOfBST(int[] sequence){
if(sequence == null || sequence.length == 0){
return false;
}
return VerifySquenceOfBST(sequence,0,sequence.length - 1);
}
/**
* 核心思路是遞歸
* 找到小于根節(jié)點(diǎn)的點(diǎn)然后遞歸
* 如果根節(jié)點(diǎn)左邊的元素大于右邊的元素直接返回false
* @param sequence
* @param left
* @param right
* @return
*/
private boolean VerifySquenceOfBST(int[] sequence,int left,int right){
//到達(dá)這部說(shuō)明遍歷的元素符合左子樹(shù)小于右子樹(shù)的規(guī)定
if(left >= right){
return true;
}
int temp = right - 1;
while(temp >= left && sequence[temp] > sequence[right]){
temp--;
}
//現(xiàn)在temp指向的是左子樹(shù)序列的最后一個(gè)元素
for(int i = temp ; i >= left ;i--){
if(sequence[i] > sequence[right])
return false;
}
return VerifySquenceOfBST(sequence,left,temp)&&
VerifySquenceOfBST(sequence,temp+1,right-1);
}
}
