剑指 Offer 33. 二叉搜索树的后序遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

思路：

---

复杂度：

递归

题解：

标准写法

class Solution {
public:
    bool traversal(vector<int>& postorder, int start, int end) {
        /* 递归终止条件 */
        if(start >= end) return true;
        int index = start;
        /* 中间处理逻辑 */
        while(postorder[index] < postorder[end]) index++;
        /* 记录分割点 */
       int midIndex = index;
        while(postorder[index] > postorder[end]) index++;
        /* 递归左右子树 */
        bool left = traversal(postorder, start, midIndex-1);
        bool right = traversal(postorder, midIndex, end-1);
        return index == end && left && right;
    }

    bool verifyPostorder(vector<int>& postorder) {
        return traversal(postorder, 0, postorder.size()-1);
    }
};