构建搜索二叉树+后序遍历

• 构建搜索二叉树->后序遍历->比较顺序
• 搜索二叉树的结构和后序遍历是一一对应的，通过逆后序遍历可以重新构建唯一的二叉树。

class Solution {
public:
    void buildTree(TreeNode* cur,TreeNode* front,int val)
    {
        if(!cur)
        {
            if(front->val<val)
            {
                front->right=new TreeNode(val);
            }
            else{
                front->left=new TreeNode(val);
            }
            return;
        }
        else if(cur->val>val)
        {
            buildTree(cur->left, cur, val);
        }
        else{
            buildTree(cur->right,cur,val);
        }

    }
    int k=0;
    void Order(TreeNode* root,vector<int>& sequence)
    {
        if(!root)
        {
            return ;
        }
        Order(root->left,sequence);
        Order(root->right,sequence);
        if(root->val==sequence[k])
        {
            k++;
        }
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(!sequence.size())
        {
            return false;
        }
        TreeNode* root=new TreeNode(sequence[sequence.size()-1]);
        TreeNode* cur=root;
        for(int i=sequence.size()-2;i>=0;i--) //n^2
        {
            cur=root;
            buildTree(cur,nullptr,sequence[i]);
        }
        //后序遍历
        Order(root,sequence);
        return k==sequence.size();
    }
};

单调栈

• 由于搜索二叉树的性质，倒序时，存在如果sequence[i]>sequence[i+1],说明sequence[i]是右节点，反之说明sequence[i]为左节点，此时进入左子树，sequence[i]到sequence[0]都小于满足小于root节点的值。
• root可能为sequence[i]/sequence的父/祖先节点，root节点的获取用栈保存，栈保存每一个节点遍历的值。
• 单独栈应用于有明确的大小关系，栈保存每一个遍历的节点值，而不需要时再弹出，省去了分辨root节点的逻辑。

#include <climits>
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty())
        {
            return false;
        }
        int root=INT_MAX;
        stack<int> s;
        for(int i=sequence.size()-1;i>=0;i--)
        {
            if(sequence[i]>root)
            return false;
            while(!s.empty()&&s.top()>sequence[i])
            {
                root=s.top();
                s.pop();
            }
            s.push(sequence[i]);
        }
        return true;
    }
};

递归法

• 搜索二叉树可以根据后序遍历重构出
• 转化成递归问题，其中第一个判断的for中要注意一定要break跳出，不然在会导致r1不更新

class Solution {
public:
    bool order(vector<int>& sequence,int l,int r)
    {
        if(l>=r)
        {
            return true;
        }
        //找出中间节点
        int root =sequence[r];
        int r1=l;
        for(int i=l;i<=r;i++)
        {
            if(sequence[i]>=root)
            {
                r1=i;
                break;
            }
        }
        //i为新l
        for(int i=r1;i<=r-1;i++)
        {
            if(sequence[i]<root) return false;
        }
        return order(sequence,l,r1-1)&&order(sequence, r1,  r-1);
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        //
        if(sequence.empty()) return false;
        return order(sequence,0,sequence.size()-1);
    }
};