题目描述： 给定一个整数数组，你需要验证它是否是一个二叉搜索树正确的先序遍历序列。 你可以假定该序列中的数都是不相同的。 参考以下这颗二叉搜索树： 示例 1： 输入: [5,2,6,1,3] 输出: false
示例 2： 输入: [5,2,1,3,6] 输出: true
进阶挑战： 您能否使用恒定的空间复杂度来完成此题？
方法1： 主要思路： （1）递归求解，时间复杂度过高；
class Solution { public: bool helper(vector<int>&preorder,int left,int right){ if(left>=right){ return true; } int mid=left+1;//找出左边界 while(mid<=right&&preorder[left]>preorder[mid]){ ++mid; } int tmp=mid; //判断右侧范围 while(tmp<=right){ if(preorder[tmp]<=preorder[left]){ return false; } ++tmp; } //递归判断左右范围 return helper(preorder,left+1,mid-1)&&helper(preorder,mid,right); } bool verifyPreorder(vector<int>& preorder) { if(preorder.size()<3){ return true; } return helper(preorder,0,preorder.size()-1); } };方法2： 主要思路： （1）单调栈； （2）由于二叉搜索的根节点的值大于左结点，小于右结点，故二叉搜索的前序遍历组成的数组，是局部递减，整体递增的数组； （3）故可以借助栈，将数组的元素压入栈中时，当小于当前栈顶的元素，则判断和之前的根节点的值大小关系，若小于，则直接返回false，否则压入栈中； （4）若大于当前栈顶的元素，则需要弹出栈中的小于当前值的元素，同时保留最后一个弹出值，作为之前的根节点值，再将当前值压入栈中；
class Solution { public: bool verifyPreorder(vector<int>& preorder) { if(preorder.size()<3){//特殊的情形 return true; } stack<int> st;//单调栈 //初始化 st.push(preorder[0]); int pre_root=INT_MIN; //遍历后面的元素值 for(int i=1;i<preorder.size();++i){ if(preorder[i]<st.top()){//若当前元素的值小于栈顶的元素 if(preorder[i]<pre_root){判断是否满足有序 return false; } st.push(preorder[i]);//压入当前元素 } else{ while(!st.empty()&&st.top()<preorder[i]){//若当前值大于栈顶的元素 pre_root=st.top();//保留最后弹出的元素 st.pop(); } st.push(preorder[i]);//压入当前的元素 } } return true; } };