文章目录

• 1. 题目
• 2. 解题
• 2.1 递归超时解
• 2.2 单调栈

1. 题目

给定一个整数数组，你需要验证它是否是一个二叉搜索树正确的先序遍历序列。

你可以假定该序列中的数都是不相同的。

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3
示例 1：
输入: [5,2,6,1,3]
输出: false

示例 2：
输入: [5,2,1,3,6]
输出: true

进阶挑战：
您能否使用恒定的空间复杂度来完成此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/verify-preorder-sequence-in-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 递归超时解

• 检查左边小于root，右边是否都大于root，时间复杂度O(n²)

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
    	if(preorder.size() <= 2) return true;
    	return check(preorder, preorder[0], 1, preorder.size()-1);
    }

    bool check(vector<int>& arr, int root, int l, int r)
    {
    	if(l>=r) return true;
    	int split = l, i;
    	while(split <= r && arr[split] < root)
    		split++;//左边部分比我root小
    	i = split;
    	for(i = split; i <= r; ++i)
    		if(arr[i] < root)//右边部分因该都比我大，此处复杂度较高
    			return false;
    	return check(arr, arr[l], l+1, split-1) && (split > r ||check(arr, arr[split], split+1, r));
    }
};

2.2 单调栈

class Solution {
	map<int,int> m;
public:
    bool verifyPreorder(vector<int>& preorder) {
    	if(preorder.size() <= 2) return true;
    	int MIN = INT_MIN;
    	stack<int> s;
    	for(int i = 0; i < preorder.size(); ++i)
    	{
    		if(preorder[i] < MIN)
    			return false;
    		while(!s.empty() && s.top() < preorder[i])//遇到大的了，右分支
    		{
    			MIN = s.top();//记录弹栈的栈顶为最小值
    			s.pop();
    		}
    		s.push(preorder[i]);
    	}
    	return true;
    }
};

100 ms 21.5 MB

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！