二叉树应用_二叉搜索树的后续遍历序列

短命女 2022-05-22 02:56 140阅读 0赞

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历序列的结果。假设输入的数组的任意两个数字都互不相同。  
分析：在二叉搜索树的后序遍历中，根节点在最后面。前面的序列可以分为两个部分：一个为左子树，小于根节点的值；一个为右子树，大于根节点的值。左子树序列和右子树序列同样应该为后序遍历序列，则可以通过递归判断是否满足。  
具体实现：

bool VerifySquenceOfBST(vector<int> sequence)
    {
        if(sequence.size()<=0)
            return false;
        vector<int> left_succ;
        vector<int> right_succ;
        int pos=0;
        int root=sequence[sequence.size()-1]
        for(;pos<sequence.size()-1;++pos)
        {
            if(sequence[pos]>root)
                break;
            left_succ.push_back(sequence[pos]);
        }
    
        for(;pos<sequrnce.size()-1;++pos)
        {
            if(sequence[pos]<root)
                return false;
            right_succ.push_back(sequence[pos]);
        }
    
        bool left_result=true;
        if(left_succ.size())
            left_result=VerifySquenceOfBST(left_succ);
    
        bool right_result=true;
        if(right_succ.size())
            right_result=VerifySquenceOfBST(right_succ);
        return left_result&&right_result;
    }
    
    //迭代的方法
    bool VerifySquenceOfBST(vector<int> sequence)
    {
       int size=sequence.size();
       if(size==0)
           return false;
       int i=0;
       while(--size)
       {
           while(sequence[i]<sequence[size])
               i++;
           while(sequence[i]>sequence[size])
               i++;
           if(i!=size)
               return false;
           i=0;
       }
       return true;
    }