二叉搜尋樹的後續遍歷

語言: CN / TW / HK

本文已參與「新人創作禮」活動,一起開啟掘金創作之路。

二叉搜尋樹的後續遍歷

題目來源: leetcode傳送門 輸入一個整數陣列,判斷該陣列是不是某二叉搜尋樹的後序遍歷結果。如果是則返回 true,否則返回 false。假設輸入的陣列的任意兩個數字都互不相同。

參考以下這顆二叉搜尋樹: c 5 / \ 2 6 / \ 1 3 示例1:

輸入: [1,6,3,2,5] 輸出: false 示例2: 輸入: [1,3,2,6,5] 輸出: true 提示: 陣列長度 <= 1000

方法一:暴力求樹的存在性

剛看到這題直接的想法就是:由於我們知道了後續遍歷,即左-右-根的序列,而且又是二叉搜尋樹,所以中序遍歷(左-根-右)的順序就是後續遍歷的的從小到大排序。為了方便,將後續遍歷翻轉,即得到了根-右-左的排序,記 lmr(left-mid-right)=中序遍歷的序列,mrl=後續遍歷的翻轉。 這樣有了lmr和mrl就可以唯一的確定一棵樹了,所以只需要根據這兩個序列能夠構造出一棵二叉樹,就可以知道後續序列是否是某個搜尋二叉樹的後續遍歷了。 具體構造樹的方法為:取mrl第一個值即為根,然後在lmr中找到根的值,左側即為左子樹,右側為右子樹,再從mrl中的第一個元素開始取lmr左子樹的個數個元素,重複完成上述操作(即遞迴求解左子樹的存在性),右子樹也是同理。如果左右子樹都存在那麼,這棵樹也就存在。要注意的是遞迴時lmr和mrl的元素必須一一對應。 程式碼如下: c vector<int> mrl; vector<int> lmr; bool check(int mrlbegin, int mrlend, int lmrbegin, int lmrend) { if(mrlend == mrlbegin && lmrend == lmrbegin) return true; else if(mrlend - mrlbegin != lmrend - lmrbegin) return false; for(int i = mrlbegin; i <= mrlend; i ++) { bool flag = false; for(int j = lmrbegin; j <= lmrend; j ++) { if(mrl[i] == lmr[j]) { flag = true; break; } } if(!flag) return false; } int root = mrl[mrlbegin]; int ptr = lmrbegin; for(; ptr <= lmrend; ptr ++) { if(lmr[ptr] == root) { break; } } if(ptr > lmrend) return false; bool ans1 = true; bool ans2 = true; if(mrlbegin + 1 >= 0 && mrlbegin + 1 <= mrlbegin + lmrend - ptr && mrlbegin + lmrend - ptr < mrl.size() && ptr + 1 <= lmrend) ans1 = check(mrlbegin + 1, mrlbegin + lmrend - ptr, ptr + 1, lmrend); if(mrlbegin + ptr - lmrbegin + 1 >= 0 && mrlbegin + lmrend - ptr + 1 <= mrlend && lmrbegin <= ptr - 1 && ptr - 1 < lmr.size()) ans2 = check(mrlbegin + lmrend - ptr + 1, mrlend, lmrbegin, ptr - 1); return ans1 && ans2; } bool verifyPostorder(vector<int>& postorder) { if(postorder.size() == 0) return true; mrl = vector<int>{}; for(int i = postorder.size() - 1; i >= 0; i --) mrl.push_back(postorder[i]); lmr = postorder; sort(lmr.begin(), lmr.end()); return check(0, mrl.size() - 1, 0, lmr.size() - 1); } 但是這樣實在是太複雜了,我在做這道題時肯定不會這樣做的(這個是我在提交後又寫的,已經通過了測試,可以放心食用,但是時間複雜度太高了,還是建議看下面的解法)

方法二:單調棧

這個解法是看到題解中有用棧的方法去解的(但是沒看具體操作方法),經過很長一段時間的思考,終於想到了這種用棧的解法,最後與題解對比,思路基本一致(方法名叫做單調棧,可能是與棧中的單調性有關),下面是具體做法。只要所有元素都遍歷完,那麼就說明此序列是一個二叉搜尋樹的後續遍歷,返回true。 程式碼如下: c bool verifyPostorder(vector<int>& postorder) { stack<int> s; int rootval = 2147483647; int cur = postorder.size() - 1; if(postorder.size() == 0) return true; else s.push(postorder[cur]); cur --; while(cur >= 0) { if(postorder[cur] > rootval) return false; if(!s.empty()) { if(postorder[cur] > s.top()) { s.push(postorder[cur]); cur --; } else { while(!s.empty() && postorder[cur] < s.top()) { rootval = s.top(); s.pop(); } } } else { s.push(postorder[cur]); cur --; } } return true; }