【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)        {            // 如果找到小于根节点直接返回false            return false;        }    }    // 判断左子树是不是二叉搜索树    bool leftIsBST = true;    if (i > 0)    {        leftIsBST = VerifySquenceOfBST(sequence, i);    }    // 判断右子树是不是二叉搜索树    bool rightIsBST = true;    if (j < length - 1)    {        // C#中无法直接操作指针，在C/C++可以直接传递sequence+i        int[] 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

设为星标，不再失联！

往期推文合集：