免费的服务器有哪些/人员优化方案

1.给定二叉树的后序遍历序列，判断是否合法

思路：1：直接递归

 bool VerifySquenceOfBST(vector<int> sequence) {//后序遍历：左右根 意味着尾部节点是根节点，//思路：先找到左右子树的分界int size=sequence.size();if(size<1)return false;if(size==1)return true;return help(sequence, 0, size-1);}bool help(vector<int> &sequence,int start,int end){if(start>=end) return true;int i=start,j=start;for(i=start;i<end;++i){if(sequence[i]>sequence[end])break;//先找到左右子树的分界}// for(;j<i;++j)查找之后意味着左子树无需再次判断了//     if(sequence[j]>sequence[i]) return false;for(j=i;j<end;++j)if(sequence[j]<sequence[end]) return false;return help(sequence,start,i-1)&&help(sequence,i,end-1);}

2.直接把递归写成循环，其时间复杂度还是O（N平方）

if (arr.empty())return false;int size = arr.size();while (--size){int i = 0;for (; i < size; ++i){if (arr[i] > arr[size])break;}for (; i < size; ++i){if (arr[i] < arr[size])return false;}}return true;}

3：后序是“左右根”，反过来就是  根右左。使用单调栈（栈中存放的要么从小到大，要么从大到小）的原理。

  bool VerifySquenceOfBST(vector<int> postorder) {//后序遍历：左右根 意味着尾部节点是根节点，//思路：先找到左右子树的分界if(postorder.size()==0){return false;}stack<int> q;int root=INT_MAX;for(int i=postorder.size()-1;i>=0;i--){if(postorder[i]>root) return false；//按根右左的顺序入栈，直到遇到第一个左节点 //判断：如果左孩子3比根节点小则根节点出栈左孩子入栈，否则报错退出while(!q.empty()&&q.top()>postorder[i]){root=q.top();q.pop();}q.push(postorder[i]);}return true;}