题目
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5 / \ 2 6 / \ 1 3
示例 1：
输入: [1,6,3,2,5] 输出: false
示例 2：
输入: [1,3,2,6,5] 输出: true
解题
方法一：递归分治
class Solution { public: vector<int> postorder; bool isTree(int left,int right){ if(left>=right) return true; int p=left; while(postorder[p]<postorder[right]) p++; int mid=p; while(postorder[p]>postorder[right]) p++; return p==right&&isTree(left,mid-1)&&isTree(mid,right-1); } bool verifyPostorder(vector<int>& postorder) { this->postorder=postorder; return isTree(0,postorder.size()-1); } };
方法二：辅助单调栈
class Solution { public: bool verifyPostorder(vector<int>& postorder) { stack<int> st; int root=INT_MAX; for(int i=postorder.size()-1;i>=0;i--){ if(postorder[i]>root) return false; while(!st.empty()&&postorder[i]<st.top()){ root=st.top(); st.pop(); } st.push(postorder[i]); } return true; } };
