C++复习之路：算法与数据结构相关12：做牛客上的剑指offer遇到的简单的基础知识（2）

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;
    }