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

原题链接：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题面：

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

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3

示例 1：

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

示例 2：

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

提示：

1. 数组长度 <= 1000

解题思路：

众所周知，二叉搜索树的特点是：每个根节点的左子树节点的值全部小于等于根节点，右子树节点的值全部大于根节点；二叉树的后序遍历顺序是左子树、右子树、根节点。根据以上，我们可以通过递归，判断所有子树的 正确性 （即其后序遍历是否满足二叉搜索树的定义） ，若所有子树都正确，则此序列为二叉搜索树的后序遍历。

递归函数：bool dfs(vector& postorder, int l, int r)。判断postorder序列中[l, r]子序列是否合法。

递归边界：l > r，代表当前子树为空，直接返回true即可。

递归工作：

        （1）得出左右子树序列：对于后序遍历序列[l, r]，postorder[r]肯定是[l, r]这个序列所代表的子树的根节点，我们从左往右找到第一个大于postorder[r]的节点postorder[m]，那么[l, m - 1]是该子树的左子树序列，[m, r - 1]是该子树的右子树序列。

        （2）判断左子树序列是否合法：根据二叉搜索树的特点，我们可知左子树序列[l, m - 1]中的每个值应该小于等于postorder[r]。这一步其实在找出m的时候已经做过了，不需要再检查一遍。

        （3）判断右子树序列是否合法：根据二叉搜索树的特点，我们可知右子树序列[m, r - 1]中的每个值应该大于postorder[r]。

        不合法则直接返回false，合法则递归判断左子树序列和右子树序列。

代码（CPP）：

class Solution {
public:
    bool dfs(vector<int>& postorder, int l, int r) {
        if (l > r) {
            return true;
        }
        // 在[l……r]序列中左往右找到第一个大于postorder[r]的
        int m = r;
        for (int i = l; i < r; i++) {
            if (postorder[i] > postorder[r]) {
                m = i;
                break;
            }
        }
        // 此时[l……m - 1]是左子树序列，[m……r - 1]是右子树序列
        // 检查左子树序列是不是每一个都小于等于postorder[r]，在第一轮遍历已经检查过了
        // 检查右子树序列是不是每一个大于postorder[r]
        int p;
        for (p = m; p < r; p++) {
            if (postorder[p] <= postorder[r]) {
                break;
            }
        }
        // 当前子树序列合法，则继续递归判断左子树序列、右子树序列
        return p == r && dfs(postorder, l, m - 1) && dfs(postorder, m, r - 1);
    }
 
    bool verifyPostorder(vector<int>& postorder) {
        return dfs(postorder, 0, postorder.size() - 1);
    }
};