輸入一個整數陣列，判斷該陣列是不是某二叉搜索樹的后序遍歷的結果，如果是則回傳true,否則回傳false，假設輸入的陣列的任意兩個數字都互不相同
解決思路
根據后序遍歷的性質，最后一個元素就是二叉搜索樹的根結點，而二叉搜索樹按中序遍歷得出的序列又是遞增有序的，從根結點可以將序列分為兩段：前一段（左子樹）都比根結點小，后一段（右子樹）都比根結點大，
因此我們知道：該后序遍歷結果序列中，所有小于根結點的都是其左子樹的結點，而大于根結點的就是其有子樹的結點，并且各自是連續的，如果條件不滿足，則回傳 false
public class Solution {
public boolean VerifySquenceOfBST(int[] sequence) {
if(sequence.length == 0) {
return false;
}
return judge(sequence, 0, sequence.length - 1);
}
public boolean judge(int[] sequence, int start, int end) {
// 比較完成，則回傳 true
if(start >= end) {
return true;
}
// 這里的值必須是 end，否則會出現空指標例外
int index = end;
// 找到分界點
while(index > start && sequence[index - 1] > sequence[end]) {
index--;
}
// 判斷分界點前是否有不滿足的數存在
for(int i = index - 1; i >= start; i--) {
if(sequence[i] > sequence[end]) {
return false;
}
}
return judge(sequence, start, index - 1) && judge(sequence, index, end - 1);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/166809.html
標籤：其他
上一篇：從上往下列印二叉樹
下一篇：二叉樹中和為某一值的路徑