題目描述

輸入一個整數(shù)數(shù)組灵再，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No蛇捌。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同务漩。

題解

若一個樹為一個二叉搜索樹，則它左子樹上的節(jié)點一定比根節(jié)點小蛤奢，右子樹上的節(jié)點一定比根節(jié)點大帅刀，且它的左右子樹一定也為二叉搜索樹。

解題思路：

1. 首先找到左子樹和右子樹的開始坐標(biāo)和結(jié)束坐標(biāo)远剩，得到左子數(shù)組和右子數(shù)組。
2. 驗證左子數(shù)組中的元素是否都小于根節(jié)點骇窍，右子數(shù)組中的元素是否都大于根節(jié)點瓜晤。
3. 若滿足條件，則進行遞歸驗證左子樹和右子樹是否都是二叉搜索樹（利用'或'門的短路性質(zhì)腹纳，子樹為空不進行判斷）痢掠。

給出兩種實現(xiàn)方法：

public boolean VerifySequenceOfBST(int[] sequence) {
    if (sequence.length == 0)
        return false;
    int len = sequence.length;
    int root = sequence[len-1];
    int leftBegin = 0, leftEnd = 0;

    // 找左子樹的開始坐標(biāo)和結(jié)束坐標(biāo)
    while (leftEnd < len-1) {
        if (sequence[leftEnd] > root)
            break;
        leftEnd++;
    }
    // 找右子樹的開始坐標(biāo)和結(jié)束坐標(biāo)
    int rightEnd = leftEnd, rightBegin = leftEnd;
    while (rightEnd < len-1) {
        if (sequence[rightEnd] < root)
            return false;
        rightEnd++;
    }
    // 得到子數(shù)組
    int[] leftArr = Arrays.copyOfRange(sequence, leftBegin, leftEnd);
    int[] rightArr = Arrays.copyOfRange(sequence, rightBegin, rightEnd);
    
    // 驗證左右子樹上的節(jié)點是否滿足二叉搜索樹的規(guī)則，不滿足直接返回false
    for (int num : leftArr)
        if (num > root) return false;
    for (int num : rightArr)
        if (num < root) return false;

    boolean left = leftArr.length == 0 || VerifySequenceOfBST(leftArr);
    boolean right = rightArr.length == 0 || VerifySequenceOfBST(rightArr);
    return left && right;
}

public boolean VerifySequenceOfBST(int[] sequence) {
    if (sequence.length == 0)
        return false;
    return VerifySequenceOfBST(sequence, 0, sequence.length-1);
}

public boolean VerifySequenceOfBST(int[] sequence, int left, int right) {
    // 當(dāng)子樹為空或子樹只有一個節(jié)點時嘲恍，直接返回true
    if (left >= right)
        return true;
    int i = right;
    // 找到右子樹的起點i
    while (i > left && sequence[i-1] > sequence[right])
        i--;
    // 從左子樹的終點開始足画，驗證左子樹是否小于根節(jié)點
    for (int j = i-1; j >= left; j--) {
        if (sequence[j] > sequence[right])
            return false;
    }
    return VerifySequenceOfBST(sequence, left, i-1) && VerifySequenceOfBST(sequence, i, right-1);
}