LeetCode二叉搜索樹的后序遍歷序列
- 題目描述
- 題目分析
- 搜索二叉樹
- 1、定義
- 2、性質
- 題目分析（續）
- 代碼實作
- 總結
題目描述
題目分析
xxxx這道題的關鍵字是“搜索二叉樹”、“后序遍歷”，后序遍歷大家應該都十分熟悉了，不熟悉的可以看我之前的博客二叉樹的常見操作，但是搜索二叉樹，估計大部分讀者都不甚了解，所以我先把搜索二叉樹的基本性質講解一下，
搜索二叉樹
1、定義
二叉搜索樹是滿足以下性質的二叉樹，
1.非空左子樹的所有結點的值小于其根結點的值；
2.非空右子樹的所有值大于其根結點的值；
3.左右子樹都是搜索二叉樹，（遞回定義）
2、性質
xxxx其實定義已經將搜索二叉樹的性質闡述的十分清楚，我再簡練得概述一下他最重要以及這道LeetCode題中考察的性質，就是按照后序順序遍歷搜索二叉樹，那么會出想這樣的序列【值均比根節點小的結點，值均比根節點大的結點，根節點】
如圖：
題目分析（續）
xxxx有了以上的知識儲備，我們就可以來仔細地分析這道題，就是通過上述提到的后序遍歷搜索二叉樹的性質，【小，大，根】，我們就可以通過比較得到左子樹的序列，得到右子樹的序列，左子樹序列中所有值都小于根，右子樹中所有值都大于根，一旦出現不符合的我們就可以斷定，這個序列是不符合搜索二叉樹的后序遍歷的，如果符合，我們我們通過剛剛確定出來的左右子樹，就可以遞回的去檢測左右子樹，一直遞回一直遞回，直到所有子樹都符合，
代碼實作
上述分析只是答題思路，具體實作細節請仔細看代碼+注釋
1、說明一下遞回子函式的引數：(1)sequence后序遍歷序列的vector (2)start檢測序列區段的開始位置 （3）檢測序列區段的結束位置
2、我們從start開始，知道找到一個比根節點大的，這樣就區分出哪一部分是左子樹區間，哪一部分是右子樹區間（從start遍歷vector，直到找到大于根的，作為左右子樹的分界）
3、這樣我們就找到一段全比根小的左子樹區間，然后再去檢測剩下的右子樹區間是否滿足都比根大，如果有比根小的，說明就不符合搜索二叉樹，就return false（再去遍歷vector的后半段）
4、如果符合，那么我們就再去遞回檢測左右子樹（此時重要的就是區間段的劃分）
class Solution {
public:
//用于遞回的子函式
bool _VerifySquenceOfBST(vector<int>& sequence,int start, int end)
{
//遞回的出口，如果，start>=end，那么區間不存在或只有一個元素，說明沒有子樹了就是true
if(start>=end)
return true;
//保存根的值
int root = sequence[end];
int i = start;
//從start開始遍歷，直到找到第一個比根大的值，作為左右子樹的分界
while(sequence[i]<root)
{
i++;
}
//從剛剛找出的分界開始，到end-1（根的前一個位置）如果出現小于根的，說明不符合規定，就回傳false
for(int j = i;j<end;j++)
{
if(sequence[j]<root)
return false;
}
//走到這里，就說明，本次檢測符合搜索二叉樹的后序遍歷，我們就需要繼續分別遞回左右子樹
//i是屬于右子樹的，所以左子樹是【start,i-1】,右子樹【i，end-1】
return _VerifySquenceOfBST(sequence,start,i-1) && _VerifySquenceOfBST(sequence,i,end-1);
}
bool VerifySquenceOfBST(vector<int> sequence) {
//如果vector為空，那么直接回傳false
if(sequence.size() == 0)
return false;
//開始遞回
return _VerifySquenceOfBST(sequence,0,sequence.size()-1);
}
};
總結
xxxx這道題考查了搜索二叉樹的后序遍歷，結果符合【左子樹（小于根），右子樹（大于根），根】這樣的結構，然后就是，二叉樹的遞回演算法，二叉樹遞回定義，遞回解決，還有一個最重要的細節，就是邊界的控制，剛剛，我們在找左右子樹分界的時候，i是第一個比根大的，所以i處于的值是屬于右子樹的，，，，
xxxx本道LeetCode題目分享就到這里，如果各位讀者有更好的解題方法或者思路，請在評論區評論，我們一起學習一起進步！
xxxx謝謝大家！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301760.html
標籤：其他