[劍指offer] 二叉搜尋樹的後序周遊序列

題目描述

輸入一個整數數組，判斷該數組是不是某二叉搜尋樹的後序周遊的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。

解題思路

二叉搜尋樹: 左子樹<根<=右子樹

對于後序周遊來說，序列數組的最後一個元素一定是根節點, 根據這個元素，将前面的數組分為左、右兩個部分，左側部分都比該元素小，右側部分都比該元素大，如果右側部分有比該根節點小的元素，那麼就不是後序周遊，如此遞歸進行。

參考代碼

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0)
            return false;
        if(sequence.length == 1)
            return true;
        return judge(sequence, 0, sequence.length-1);
    }
    public boolean judge(int [] sequence, int start, int root){
        if(start >= root)
            return true;
        int i = start;
        while(i < root && sequence[i] < sequence[root])
            i++;
        for(int j=i; j<root; j++){
            if(sequence[j]<sequence[root])
                return false;
        }
        return (judge(sequence, start, i-1)) && (judge(sequence, i, root-1));
    }
}