劍指Offer面試題：22.二叉搜索樹(shù)的后序遍歷序列

題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。如果是則返回true，否則返回false。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。例如在下面的一顆二叉搜索樹(shù)中，輸入數(shù)組{5,7,6,9,11,10,8}，則返回true，因?yàn)檫@個(gè)整數(shù)序列是下圖二叉搜索樹(shù)的后序遍歷結(jié)果。如果輸入的數(shù)組是{7,4,6,5}，由于沒(méi)有哪棵二叉搜索樹(shù)的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。

一、題目：二叉搜索樹(shù)的后序遍歷序列

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

　　例如在下面的一顆二叉搜索樹(shù)中，輸入數(shù)組{5,7,6,9,11,10,8}，則返回true，因?yàn)檫@個(gè)整數(shù)序列是下圖二叉搜索樹(shù)的后序遍歷結(jié)果。如果輸入的數(shù)組是{7,4,6,5}，由于沒(méi)有哪棵二叉搜索樹(shù)的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。

二、解題思路

2.1 核心步驟

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

　　因此，我們可以總結(jié)出算法步驟：

　　Step1.通過(guò)取出序列最后一個(gè)元素得到二叉搜索樹(shù)的根節(jié)點(diǎn)；

　　Step2.在二叉搜索樹(shù)中左子樹(shù)的結(jié)點(diǎn)小于根結(jié)點(diǎn)，因此可以遍歷一次得到左子樹(shù)；

　　Step3.在二叉搜索樹(shù)中右子樹(shù)的結(jié)點(diǎn)大于根結(jié)點(diǎn)，因此可以繼續(xù)遍歷后序元素得到右子樹(shù)；

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

2.2 代碼實(shí)現(xiàn)

    public static bool VerifySquenceOfBST(int[] sequence, int length)
    {
        if (sequence == null || length <= 0)
        {
            return false;
        }

        int root = sequence[length - 1];

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

        return leftIsBST && rightIsBST;
    }

三、單元測(cè)試

3.1 測(cè)試用例

    //            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);
    }

    // 樹(shù)中只有1個(gè)結(jié)點(diǎn)
    [TestMethod]
    public void SequenceTest5()
    {
        int[] data = { 5 };
        bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);
        Assert.AreEqual(result, true);
    }

    // 錯(cuò)誤序列
    [TestMethod]
    public void SequenceTest6()
    {
        int[] data = { 7, 4, 6, 5 };
        bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);
        Assert.AreEqual(result, false);
    }

    // 錯(cuò)誤序列
    [TestMethod]
    public void SequenceTest7()
    {
        int[] data = { 4, 6, 12, 8, 16, 14, 10 };
        bool result = SequenceHelper.VerifySquenceOfBST(data, data.Length);
        Assert.AreEqual(result, false);
    }

    // 錯(cuò)誤序列
    [TestMethod]
    public void SequenceTest8()
    {
        bool result = SequenceHelper.VerifySquenceOfBST(null, 0);
        Assert.AreEqual(result, false);
    }