劍指offer 二叉搜尋樹的後序遍歷序列

2022-11-24 15:11:30 字數 970 閱讀 2376

輸入一個整數陣列,判斷該陣列是不是某二叉搜尋樹的後序遍歷的結果。如果是則輸出yes,否則輸出no。假設輸入的陣列的任意兩個數字都互不相同。

分析:如果一個陣列是一個二叉搜尋樹的後序遍歷結果,那麼這個陣列有以下特徵:陣列的最後一個元素是(子)樹的根節點,前面的部分可以分為兩個部分,前一部分的元素都小於最後一個元素值,後一部分都大於陣列最後一個元素值,我們首先需要找到這個臨界值,在判斷前一部分的元素是否都小於陣列末尾的值,接著分別對陣列前兩部分處理,(遞迴定義)。

1

class

solution

7int i = r - 1;8

//i指向第一個小於陣列末尾值的元素下標

9while (i >= l && sequence[i] >sequence[r])

12//

判斷前半部分所有元素值是否都小於陣列末尾值

13for (int j = i; j >= l; j--) 17}

18return judge(sequence, l, i) && judge(sequence, i + 1, r - 1

);19}20

public:21

bool verifysquenceofbst(vectorsequence) else28}

29 };

2019.08.11

1

class

solution

12int j =i;

13for (; j < right; j++)

17return verifysquenceofbst(sequence, left, i - 1) && verifysquenceofbst(sequence, i, right - 1

);18}19

public:20

bool verifysquenceofbst(vectorsequence)

26 };

劍指offer 序列化二叉樹

請實現兩個函式,分別用來序列化和反序列化二叉樹 二叉樹的序列化是指 把一棵二叉樹按照某種遍歷方式的結果以某種格式儲存為字串,從而使得記憶體中建立起來的二叉樹可以持久儲存。序列化可以基於先序 中序 後序 層序的二叉樹遍歷方式來進行修改,序列化的結果是一個字串,序列化時通過 某種符號表示空節點 以 表示...

劍指offer 31序列化二叉樹

請實現兩個函式,分別用來序列化和反序列化二叉樹 二叉樹的序列化是指 把一棵二叉樹按照某種遍歷方式的結果以某種格式儲存為字串,從而使得記憶體中建立起來的二叉樹可以持久儲存。序列化可以基於先序 中序 後序 層序的二叉樹遍歷方式來進行修改,序列化的結果是一個字串,序列化時通過 某種符號表示空節點 以 表示...

劍指Offer 37 序列化二叉樹

請實現兩個函式,分別用來序列化和反序列化二叉樹。你可以將以下二叉樹 1 2 3 4 5 序列化為 1,2,3,null,null,4,5 class codec res 空格為分隔符 return res decodes your encoded data to tree.treenode dese...