劍指offer - 二叉搜尋樹後序周遊序列

二叉搜尋樹後序周遊序列

• 題目描述
• 算法思路
• 代碼實作

題目描述

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

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

示例

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

算法思路

二叉搜尋樹的特點：左子樹所有節點小于根節點，右子樹的所有節點大于根節點。它的子樹也遵循這個規律。

樹的後序周遊順序是：左子樹、右子樹、根

由上面兩個特點可以得出以下思路：

1. 定義左右指針 left=0，right=nums.length-1，遞歸周遊，當 left>=right ，說明此時隻有一個節點，傳回true
2. 定義一個移動指針 k=left，當nums[k] < nums[right]（根節點）時，一直往右移，即k++
3. 當 k 不動時，說明此時nums[k] > nums[right]，說明右子樹開始了，記錄這個k的值，它是此刻右子樹的開始
4. 當 nums[k] > nums[right]時，k++，當 k=right時，停止。說明目前這棵樹符合 左子樹的所有節點 < 根節點，右子樹的所有節點 > 根節點。
5. 遞歸周遊，看它子樹是否滿足左子樹的所有節點 < 根節點，右子樹的所有節點 > 根節點。

代碼實作

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int n = sequence.length;
        if(n==0) return false;
        return recur(sequence,0,n-1);
    }
    
    private boolean recur(int [] nums,int left,int right){
        //遞歸終止條件
        if(left>=right) return true;
        int k = left;
        //左子樹小于根節點
        while(nums[k]<nums[right]) k++;
        //找到切分左右子樹的臨界點
        int mid = k;
        //右子樹大于根節點
        while(nums[k]>nums[right]) k++;
        //遞歸周遊
        return k==right && recur(nums,left,mid-1) && recur(nums,mid,right-1);
        
    }
}