樹-二叉搜尋樹的後序周遊序列-JZ23

描述

輸入一個整數數組，判斷該數組是不是某二叉搜尋樹的後序周遊的結果。如果是則傳回true,否則傳回false。假設輸入的數組的任意兩個數字都互不相同。（ps：我們約定空樹不是二叉搜尋樹）

示例1

輸入： [4,8,6,12,16,14,10]

傳回值： true

思路

1.二叉搜尋樹：左子樹全部小于根節點，右子樹全部大于根節點

2.後序周遊：左子樹 -> 右子樹 -> 根節點，做後一個節點是根節點

3.我們可以将一個序列劃分為3段, 左子樹+右子樹+根, 例如[4, 8, 6, 12, 16, 14, 10]可以根據根節點的值将其劃分為左子樹[4, 8, 6], 右子樹[12, 16, 14], 根[10],

4.代碼中可以先确定的右子樹區間, 是以當左子樹區間中出現大于根節點的值時, 序列不合法, 我們再采用分治的思想, 對于每段序列代表的子樹, 檢查它的左子樹和右子樹, 當且僅當左右子樹都合法時傳回true

代碼

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0) {
            return false;
        }
        return check(sequence, 0, sequence.length - 1);
    }
    //檢查數組中left到right是不是二叉搜尋樹
    public boolean check(int [] sequence, int left, int right) {
        if (left >= right) {
            //隻有一個節點
            return true;
        }
        int root = sequence[right];
        int index = right - 1;//定義的左子樹的右邊界
        while (index >= 0 && sequence[index] > root) {
            index--;
        }
        //檢查左子樹是否有大于根節點的
        for (int i = left; i <= index; i++) {
            if (sequence[i] > root) {
                return false;
            }
        }
        return check(sequence, left, index) && check(sequence, index+1, right-1);
    }
}