描述

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

示例 1：

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

示例 2：

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

题解

这道题的具体解法，可参看 这个B站视频

  1. class Solution {
  2. public:
  3.     bool verifyPostorder(vector<int>& postorder) {
  4.         if(postorder.empty()) return true;
  5.         return dfs(postorder, 0, postorder.size() - 1);
  6.     }
  7.     bool dfs(vector<int>& postorder, int l, int r) {
  8.         if(l >= r) return true; 
  9.         int p = l; 
  10.         while(postorder[p] < postorder[r]) p++;
  11.         int m = p; // 此时的postorder[p]大于postorder[r], [l, m - 1]是左子树 
  12.         while(postorder[p] > postorder[r]) p++; 
  13.         return p == r && dfs(postorder, l, m - 1) && dfs(postorder, m, r - 1);
  14.     }
  15. };