【C#刷題】|?作者?/ Edison Zhou

這是EdisonTalk的第289篇原創內容

---

我們來用之前學到的數據結構知識來刷《劍指Offer》的一些核心題目（精選了其中30+道題目），希望對你有幫助！本文題目為：二叉搜索樹的后序遍歷序列。

1題目介紹

題目：輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。如果是則返回true，否則返回false。假設輸入的數組的任意兩個數字都互不相同。

例如在下面的一顆二叉搜索樹中，輸入數組{5,7,6,9,11,10,8}，則返回true，因為這個整數序列是下圖二叉搜索樹的后序遍歷結果。如果輸入的數組是{7,4,6,5}，由于沒有哪棵二叉搜索樹的后序遍歷的結果是這個序列，因此返回false。

2解題思路與實現

思路：

在后序遍歷得到的序列中，最后一個數字是樹的根結點的值。數組中前面的數字可以分為兩部分：第一部分是左子樹結點的值，它們都比根結點的值小；第二部分是右子樹結點的值，它們都比根結點的值大。

因此，我們可以總結出算法步驟：

Step1.通過取出序列最后一個元素得到二叉搜索樹的根節點；

Step2.在二叉搜索樹中左子樹的結點小于根結點，因此可以遍歷一次得到左子樹；

Step3.在二叉搜索樹中右子樹的結點大于根結點，因此可以繼續遍歷后序元素得到右子樹；

Step4.重復以上步驟遞歸判斷左右子樹是不是二叉搜索樹，如果都是，則返回true，如果不是，則返回false;

實現：

public static bool VerifySquenceOfBST(int[] sequence, int length) {if (sequence == null || length <= 0){return false;}int root = sequence[length - 1];int i = 0;// 在二叉搜索樹中左子樹的結點小于根結點for (; i < length - 1; i++){if (sequence[i] > root){break;}}// 在二叉搜索樹中右子樹的結點大于根結點int j = i;for (; j < length - 1; j++){if (sequence[j] < root){// 如果找到小于根節點直接返回falsereturn false;}}// 判斷左子樹是不是二叉搜索樹bool leftIsBST = true;if (i > 0){leftIsBST = VerifySquenceOfBST(sequence, i);}// 判斷右子樹是不是二叉搜索樹bool rightIsBST = true;if (j < length - 1){// C#中無法直接操作指針，在C/C++可以直接傳遞sequence+iint[] newSequence = sequence.Skip(i).ToArray();rightIsBST = VerifySquenceOfBST(newSequence, length - i - 1);}return leftIsBST && rightIsBST; }

3單元測試

單元測試用例：

// 10 // / \ // 6 14 // /\ /\ // 4 8 12 16 [TestMethod] public void SequenceTest1() {int[] data = { 4, 8, 6, 12, 16, 14, 10 };bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);Assert.AreEqual(result, true); }// 5 // / \ // 4 7 // / // 6 [TestMethod] public void SequenceTest2() {int[] data = { 4, 6, 7, 5 };bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);Assert.AreEqual(result, true); }// 5 // / // 4 // / // 3 // / // 2 // / // 1 [TestMethod] public void SequenceTest3() {int[] data = { 1, 2, 3, 4, 5 };bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);Assert.AreEqual(result, true); }// 1 // \ // 2 // \ // 3 // \ // 4 // \ // 5 [TestMethod] public void SequenceTest4() {int[] data = { 5, 4, 3, 2, 1 };bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);Assert.AreEqual(result, true); }// 樹中只有1個結點 [TestMethod] public void SequenceTest5() {int[] data = { 5 };bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);Assert.AreEqual(result, true); }// 錯誤序列 [TestMethod] public void SequenceTest6() {int[] data = { 7, 4, 6, 5 };bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);Assert.AreEqual(result, false); }// 錯誤序列 [TestMethod] public void SequenceTest7() {int[] data = { 4, 6, 12, 8, 16, 14, 10 };bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);Assert.AreEqual(result, false); }// 錯誤序列 [TestMethod] public void SequenceTest8() {bool result = SequenceHelper.VerifySquenceOfBST(null, 0);Assert.AreEqual(result, false); }

測試結果：

測試的結果情況如下圖：

Ref參考資料

何海濤，《劍指Offer》

后臺回復：劍指offer，即可獲得pdf下載鏈接喲！

????掃碼關注EdisonTalk

設為星標，不再失聯！

往期推文合集：2020年上半年推文合集

總結

以上是生活随笔為你收集整理的C#刷剑指Offer | 二叉搜索树的后序遍历序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。