1. 題目
2. 解題思路
3. 資料型別功能函式總結
4. java代碼
5. 踩坑小記
- 遞回呼叫，顯示StackOverflowError

1. 題目

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

參考以下這顆二叉搜索樹：

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

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

提示：

陣列長度 <= 1000

作者：Krahets
鏈接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vwxx5/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

2. 解題思路

使用遞回分治的思路：

根據最后一個值x，劃分為左右子陣列;
- 查找比x大的元素，第一個比x大的元素下標為i，在此處劃分陣列[start,i-1]和[i,end]；
檢查左右陣列：左陣列的元素均小于x，右陣列的元素均大于x，
- 由于左陣列元素和x的大小關系已經確定，只需要檢查右陣列和x的大小關系即可，
- 如果右陣列不符合要求，直接回傳false；否則繼續執行下一步
對左右子陣列，重復上述步驟;

終止條件：陣列為慷訓者只有一個元素，回傳true

3. 資料型別功能函式總結

//陣列
int len=arrayname.length;//陣列長度

4. java代碼

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder,0,postorder.length-1);
    }
    public boolean recur(int[] postorder,int start,int end){
        if(end-start<=1){
            return true;
        }
        else{
            int root_val=postorder[end];
            int i=start;
            for(i=start;i<end;i++){
                if(postorder[i]>root_val){
                    break;
                }
            }
            //得到i,左右陣列[start,i-1],[i,end-1]
            //檢查左右陣列
            int flag=0;
            for(int j=i;j<end && flag==0;j++){
                if(postorder[j]<root_val){
                    flag=1;
                }
            }
            if(flag==0){
                return  recur(postorder,start,i-1)&&recur(postorder,i,end-1);
            }
            else{
                return false;
            }

        }
    }
}

5. 踩坑小記

遞回呼叫，顯示`StackOverflowError`

遞回函式的部分為：

if(flag==0){
    return  recur(postorder,start,i-1)&&recur(postorder,i,end-1);
}

而我一開始寫成了：

if(flag==0){
    return  recur(postorder,start,i-1)&&recur(postorder,i,end);
}

然后一直報錯顯示StackOverflowError，后來發現是右陣列劃分的時候，傳入end就會導致后序遍歷一直停留在和根節點的比較上，無法退出回圈，導致堆疊溢位，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550868.html

標籤：其他

上一篇：Jmeter測驗工具-測驗基礎（4）-引數化及控制器等

下一篇：返回列表