《劍指offer》——33. 二叉搜尋樹的後序周遊序列

難度：中等

題目

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

 

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

     5
    / \
   2   6
  / \
 1   3
示例 1：

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

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

提示：

數組長度 <= 1000
           

解答

思路

遞歸。
後序周遊，根節點在最後面。
隻要數組可以不斷的被根節點分成兩部分，左邊小于根節點，右邊大于根節點。則這個數組是二叉搜尋樹的後序周遊。
           

知識點

疊代器的使用
           

複雜度	O
時間複雜度	O(n)
空間複雜度	O(n)

代碼

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return verifyPostorderCore(postorder.begin(),postorder.end());
    }

        bool verifyPostorderCore(vector<int>::iterator begin, vector<int>::iterator end) {
        if(end-begin<=1)
        {
            return true;
        }

        int root=*(end-1);
        vector<int>::iterator mid=end-1;
        for(auto it=begin;it<end;it++)
        {
            if(*it>root)
            {
                mid=it;
                break;
            }
        }
        for(auto it=mid+1;it<end;it++)
        {
            if(*it<root)
            {
                return false;
            }
        }
        return (verifyPostorderCore(begin,mid))&&(verifyPostorderCore(mid,end-1));

    }
};