剑指offer：二叉搜索树的后序遍历序列（判断一个数组是否是二叉搜索树的后续遍历序列）

迈不过友情╰ 2022-08-05 08:47 121阅读 0赞

**题目描述**

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

#include <stdlib.h>
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <stack>
    #include <queue>
    
    using namespace std;
    
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };
    class Solution {
    public:
        bool VerifySquenceOfBST(vector<int> sequence) {
    		int part = 0, i = 0;
    
    		if(sequence.empty())
    		{
    			return false;
    		}
    		
    		return isSeqBST(sequence,0,sequence.size());
        }
    
    	bool isSeqBST(vector<int> sequence, int start, int end)
    	{
    		int i = 0 , j = 0;
    		bool left = true, right = true;
    		int root = 0;
    
    		if((end-start) <= 0)
    		{
    			return false;
    		}
    
    		i = start;
    		root = sequence[end-1];
    		/* 找出左子树的节点 */
    		for(; i < end-1; i++)
    		{
    			if(sequence[i] > root)
    			{
    				break;
    			}
    		}
    
    		/* 判断右子树是否符合要求 */
    		for(j = i; j < end-1;j++)
    		{
    			if(sequence[j] < root)
    			{
    				return false;
    			}
    		}
    		
    		/* 判断左子树是否符合线索二叉树 */
    		left = true;
    		if(i > start)
    		{
    			left = isSeqBST(sequence,start,i);
    		}
    
    		/* 判断右子树是否符合线索二叉树 */
    		right = true;
    		if(i < end-1)
    		{
    			right = isSeqBST(sequence,i,end-1);
    		}
    
    		return (left&&right);
    	}
    };
    
    
    int main(void)
    {
    	int a[7] = {4,8,6,12,16,14,10};
    	vector<int> vec(a,a+7);
    	Solution s;
    
    	if(s.isSeqBST(vec,0,7) == true)
    	{
    		cout << "true" << endl;
    	}
    	else
    	{
    		cout << "false" << endl;
    	}
    
    	return 0;
    }