在后序遍歷得到的序列中, 最后一個(gè)數(shù)字是樹(shù)的根結(jié)點(diǎn)的值。數(shù)組中前面的數(shù)字可以分為兩部分: 第一部分是左子樹(shù)結(jié)點(diǎn)的值,它們都比根結(jié)點(diǎn)的值?。?第二部分是右子樹(shù)結(jié)點(diǎn)的值,它們都比根結(jié)點(diǎn)的值大。
public class Test24 {
/**
* 輸入一個(gè)整數(shù)數(shù)組,判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。
* 如果是則返回true。否則返回false。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
*
* @param sequence 某二叉搜索樹(shù)的后序遍歷的結(jié)果
* @return true:該數(shù)組是某二叉搜索樹(shù)的后序遍歷的結(jié)果。false:不是
*/
public static boolean verifySequenceOfBST(int[] sequence) {
// 輸入的數(shù)組不能為空,并且有數(shù)據(jù)
if (sequence == null || sequence.length <= 0) {
return false;
}
// 有數(shù)據(jù),就調(diào)用輔助方法
return verifySequenceOfBST(sequence, 0, sequence.length - 1);
}
/**
* 輸入一個(gè)整數(shù)數(shù)組,判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。
* 【此方法與上一個(gè)方法不同,未進(jìn)行空值判斷,對(duì)于數(shù)組度為0的情況返回的true也于上題不同,
* 此方法只是上面一個(gè)方法的輔助實(shí)現(xiàn),對(duì)于數(shù)數(shù)組為null和數(shù)組長(zhǎng)度為0的情況,執(zhí)行結(jié)果并非相同】
* 【也就是說(shuō)此方法只有數(shù)組中有數(shù)據(jù)的情況下才與上面的方法返回同樣的結(jié)點(diǎn),
* verifySequenceOfBST(sequence) ===
* verifySequenceOfBST(sequence, 0, sequence.length - 1)
* 當(dāng)sequence中有數(shù)據(jù)才成立
* 】
*
* @param sequence 某二叉搜索樹(shù)的后序遍歷的結(jié)果
* @param start 處理的開(kāi)始位置
* @param end 處理的結(jié)束位置
* @return true:該數(shù)組是某二叉搜索樹(shù)的后序遍歷的結(jié)果。false:不是
*/
public static boolean verifySequenceOfBST(int[] sequence, int start, int end) {
// 如果對(duì)應(yīng)要處理的數(shù)據(jù)只有一個(gè)或者已經(jīng)沒(méi)有數(shù)據(jù)要處理(start>end)就返回true
if (start >= end) {
return true;
}
// 從左向右找第一個(gè)不大于根結(jié)點(diǎn)(sequence[end])的元素的位置
int index = start;
while (index < end - 1 && sequence[index] < sequence[end]) {
index++;
}
// 執(zhí)行到此處[end, index-1]的元素都是小于根結(jié)點(diǎn)的(sequence[end])
// [end, index-1]可以看作是根結(jié)點(diǎn)的左子樹(shù)
// right用于記錄第一個(gè)不小于根結(jié)點(diǎn)的元素的位置
int right = index;
// 接下來(lái)要保證[index, end-1]的所有元素都是大于根根點(diǎn)的【A】
// 因?yàn)閇index, end-1]只有成為根結(jié)點(diǎn)的右子樹(shù)
// 從第一個(gè)不小于根結(jié)點(diǎn)的元素開(kāi)始,找第一個(gè)不大于根結(jié)點(diǎn)的元素
while (index < end - 1 && sequence[index] > sequence[end]) {
index++;
}
// 如果【A】條件滿足,那么一定有index=end-1,
// 如果不滿足那說(shuō)明根結(jié)點(diǎn)的右子樹(shù)[index, end-1]中有小于等于根結(jié)點(diǎn)的元素,
// 不符合二叉搜索樹(shù)的定義,返回false
if (index != end - 1) {
return false;
}
// 執(zhí)行到此處說(shuō)明直到目前為止,還是合法的
// [start, index-1]為根結(jié)點(diǎn)左子樹(shù)的位置
// [index, end-1]為根結(jié)點(diǎn)右子樹(shù)的位置
index = right;
return verifySequenceOfBST(sequence, start, index - 1) && verifySequenceOfBST(sequence, index, end - 1);
}
public static void main(String[] args) {
// 10
// / \
// 6 14
// /\ /\
// 4 8 12 16
int[] data = {4, 8, 6, 12, 16, 14, 10};
System.out.println("true: " + verifySequenceOfBST(data));
// 5
// / \
// 4 7
// /
// 6
int[] data2 = {4, 6, 7, 5};
System.out.println("true: " + verifySequenceOfBST(data2));
// 5
// /
// 4
// /
// 3
// /
// 2
// /
// 1
int[] data3 = {1, 2, 3, 4, 5};
System.out.println("true: " + verifySequenceOfBST(data3));
// 1
// \
// 2
// \
// 3
// \
// 4
// \
// 5
int[] data4 = {5, 4, 3, 2, 1};
System.out.println("true: " + verifySequenceOfBST(data4));
// 樹(shù)中只有1個(gè)結(jié)點(diǎn)
int[] data5 = {5};
System.out.println("true: " + verifySequenceOfBST(data5));
int[] data6 = {7, 4, 6, 5};
System.out.println("false: " + verifySequenceOfBST(data6));
int[] data7 = {4, 6, 12, 8, 16, 14, 10};
System.out.println("false: " + verifySequenceOfBST(data7));
}
}
http://wiki.jikexueyuan.com/project/for-offer/images/31.png" alt="" />