题解 | #二叉搜索树的后序遍历序列#

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
            
  tree* head;
        if(sequence.empty())
        return false;
        replace(sequence, head);


        houxubianli(head);
        cout<<"here is ok"<<endl;
        auto p1 = sequence.begin();
        auto p2 = hx.begin();
        auto p3=zx.begin();
        for(auto i:hx)
        cout<<i<<':';
        for(auto i:hx)
        cout<<i<<'~';

        int j = sequence.size();

        for (int i = 0; i < j; i++)
        {
            if(i<j-1)
            if(*(p3+i)>*(p3+i+1))
            return false;
            cout<<*(p2+i)<<endl;
            if (*(p1 + i) != *(p2 + i))
                return false;
        }
        return true;



    }




////////////////////////////////////////////////////////////////////////////
/////////////////////////////////服务函数
  
  
      vector <int> hx;
      vector <int> zx;
  
  
  
  
  struct tree
{
    struct tree *left;
    struct tree *right;
    int val;
};


  
  
  
  
  
  ///////////////////////////////////////////////////
  /*之前的想法就是，根据后序遍历还原搜索二叉树，然后再后序遍历，和输出的数组对比来确定*/
  /*但是现在有个问题，就是还原的树可能不是搜索二叉树，那肯定就是false的，但是后序遍历的对比是没问题*/
/*所以就在后序遍历中，增加对搜索二叉树的判断*/

      void houxubianli(tree *head)
    {
            if(head)
    {
        
        if(head->left)
        houxubianli(head->left);
        cout<<head->val<<':'<<endl;
        zx.push_back(head->val);
        
        if(head->right)
         houxubianli(head->right);

        hx.push_back(head->val);
        cout<<head->val<<'-'<<endl;
        
    }

    }
  
  
  
  
  
  
    int replace(vector<int> sequence,tree* &head)
    {
        auto point = sequence.begin();                    //point为迭代器，指向最后一个元素

        int hou = sequence.size()-1;
        int qian = 0;
        point = point + hou;


        tree* p1 = new tree;                                     //给新的节点开辟一个空间
        head = p1;
        head->val = *point;
        head->left=nullptr;
        head->right=nullptr;
        cout<<head->val<<endl;



        if (hou<=0||qian>=hou)
        {

            return 1;
        }
        /*寻找左子树*/
        for (int i = 1; hou-i>=0; i++) 
            if (*(point - i) < *(point))
            {

                vector<int> var(sequence.begin()+qian,sequence.begin()+hou-i+1);
                qian = hou - i+1;
                replace(var, head->left);
                break;
            }

        /*寻找右子树*/
        if (*point < *(point - 1))
        {
            vector<int> var2(sequence.begin() + qian, sequence.begin() + hou);
            replace(var2, head->right);

        }

        return 1;

    }











};

这道题我一开始我的想法时,先根据数组的构建搜索二叉树,再后序遍历对比

要还原搜索二叉树,必须先找出后序遍历的搜索二叉树数组的规律.

1.根节点在数组的最后

2.节点是否有子树就看左边有没有数

3.节点如果有右子树,则左边第一个数就是他,必须大于它

4节点如果有左子树,则左边有小于它的树,也是第一个(从右往左第一个)

然后发现,根据数组构建的二叉树,后序遍历出来的二叉树,后序遍历还是数组本身

所以这个时候,根据搜索二叉树的中序遍历,数是递增的排列来判断.