二叉搜索樹的后序遍歷序列

題目描述

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

image

示例：

輸入: [1,6,3,2,5]
輸出: false

輸入: [1,3,2,6,5]
輸出: true

提示：
數(shù)組長度 <= 1000

轉載來源：力扣（LeetCode）

題目分析

1. 二叉搜索樹的特點：
   1.1. 左子樹的所有節(jié)點永遠小于等于父節(jié)點
   1.2. 右子樹的所有節(jié)點永遠大于等于右子樹
   1.3. 左子樹和右子樹也是二叉搜索樹
2. 后續(xù)遍歷的特點：左子樹先遍歷、右子樹后遍歷、父節(jié)點最后遍歷

舉例子： [1,3,2,6,5]

• 根據(jù)特點2，根節(jié)點顯然是5
• 根據(jù)特點1.2，我們可以從根節(jié)點往前探索，比它大的都是右子樹的，剩下的都是左子樹的，所以右子樹是[6]，左子樹是[1,3,2]
• 然后對于特點1.1還沒有得到驗證，所有對于左子樹[1,3,2]，都必須確保每個元素都比5小，否則不符合二叉搜索樹的特點，返回false
• 如果特點1.1得到驗證，那么只要證明特點1.3，整棵樹就是滿足二叉搜索樹的特點了，1.3的證明很簡單，對左子樹和右子樹也進行像整棵樹一樣的操作即可（遞歸）

    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length == 1) return true;
        return verifyPostorder(postorder,0,postorder.length-1);
    }
    
    //驗證當前數(shù)是否為二叉搜索樹
    public boolean verifyPostorder(int[] postorder,int head,int tail) {
        if(head >= tail) return true;
        int parent = postorder[tail];  
        int rightHead = tail;
        //尋找右子樹和左子樹的分界點
        while(rightHead >= head){
            if(postorder[rightHead] >= parent)
                rightHead--;
            else
                break;
        }
        rightHead += 1;
        // 驗證右子樹是否為二叉搜索樹
        if(!verifyPostorder(postorder,rightHead,tail-1))
            return false;
        // 驗證左子樹是否都比父節(jié)點小
        if(!verifyLeft(postorder,head,rightHead-1,parent))
            return false;
        // 驗證左子樹是否為二叉搜索樹
        return verifyPostorder(postorder,head,rightHead-1);
    }

    public boolean verifyLeft(int[] postorder,int head,int tail,int parent){
        for(int i = head; i <= tail; i++){
            if(postorder[i] > parent)
                return false;
        }
        return true;
    }