文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 遞歸超時解
    • 2.2 單調(diào)棧

1. 題目

給定一個整數(shù)數(shù)組，你需要驗(yàn)證它是否是一個二叉搜索樹正確的先序遍歷序列。

你可以假定該序列中的數(shù)都是不相同的。

參考以下這顆二叉搜索樹：5/ \2 6/ \1 3 示例 1： 輸入: [5,2,6,1,3] 輸出: false示例 2： 輸入: [5,2,1,3,6] 輸出: true進(jìn)階挑戰(zhàn)： 您能否使用恒定的空間復(fù)雜度來完成此題？

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/verify-preorder-sequence-in-binary-search-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

2.1 遞歸超時解

• 檢查左邊小于root，右邊是否都大于root，時間復(fù)雜度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)//右邊部分因該都比我大，此處復(fù)雜度較高return false;return check(arr, arr[l], l+1, split-1) && (split > r ||check(arr, arr[split], split+1, r));} };

2.2 單調(diào)棧

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/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 255. 验证前序遍历序列二叉搜索树（单调栈）*的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。