劍指offer專題地址

劍指offer索引地址

題目描述

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

解決方法

根據(jù)后序遍歷特點(diǎn)，數(shù)值由小到大再變小，來進(jìn)行檢驗(yàn)。

public class Solution {
    public boolean VerifySquenceOfBST(int[] sequence) {
        int size = sequence.length;
        if (0 == size) return false;
        int i = 0;
        while (--size > 0) {
            while (sequence[i++] < sequence[size] && i < size) ;
            while (sequence[i++] > sequence[size] && i < size) ;

            if (i < size) return false;
            i = 0;
        }
        return true;
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)。
• 空間復(fù)雜度：O(1)。

哎呀，如果我的名片丟了。微信搜索“全菜工程師小輝”，依然可以找到我