題目描述

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

思路

1.二叉搜索樹（二叉排序樹）的特點是左節(jié)點<根<右節(jié)點（左子樹<根<右子樹），數(shù)組的左右一個元素為根節(jié)點
2.根節(jié)點的前面可分成兩部門，前一部分（左子樹）的值均小于根，后一部分（右子樹）的值均大于根

代碼

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