JZ33 二叉搜索樹的後序遍歷序列

描述

輸入一個整數數組，判斷該數組是不是某二叉搜索樹的後序遍歷的結果。如果是則返回 true ,否則返回 false 。假設輸入的數組的任意兩個數字都互不相同。
提示：
1.二叉搜索樹是指父親節點大於左子樹中的全部節點，但是小於右子樹中的全部節點的樹。
2.該題我們約定空樹不是二叉搜索樹
3.後序遍歷是指按照 “左子樹-右子樹-根節點” 的順序遍歷

思路

BST的後序序列的合法序列是，對於一個序列S，最後一個元素是x （也就是根），如果去掉最後一個元素的序列為T，
那麼T滿足：T可以分成兩段，前一段（左子樹）小於x，後一段（右子樹）大於x，
且這兩段（子樹）都是合法的後序序列。完美的遞歸定義

代碼

package mid.JZ33二叉搜索樹的後序遍歷序列;

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) return false;
        return judge(sequence, 0, sequence.length - 1);
    }

    public boolean judge(int[] sequence, int start, int end) {
        //為空
        if (start >= end) return true;

        //根節點
        int root = sequence[end];
        int i = start;

        //左子樹遍歷
        while (i <= end && sequence[i] < root) {
            i++;
        }

        //右子樹
        for (int j = i; j < end; j++) {
            if (sequence[j] < root) return false;
        }

        //左子樹 與 右子樹遞歸
        /**
         * i 是右子樹第一個元素
         * 左側 start開始，i-1結束
         * 右側 i開始，end-1是減去當前根元素
         */
        return judge(sequence, start, i - 1) && judge(sequence, i, end - 1);
    }
}