剑指Offer面试题：22.二叉搜索树的后序遍历序列

妖狐艹你老母 2021-11-22 19:18 274阅读 0赞

# 一、题目：二叉搜索树的后序遍历序列 #

> **题目：**输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
> 
> 　　例如在下面的一颗二叉搜索树中，输入数组\{5,7,6,9,11,10,8\}，则返回true，因为这个整数序列是下图二叉搜索树的后序遍历结果。如果输入的数组是\{7,4,6,5\}，由于没有哪棵二叉搜索树的后序遍历的结果是这个序列，因此返回false。
> 
> ![381412-20150903221345825-2126716036.jpg][]

# 二、解题思路 #

## 2.1 核心步骤 ##

在后序遍历得到的序列中，**最后一个数字是树的根结点的值**。数组中前面的数字可以分为两部分：**第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大**。

因此，我们可以总结出算法步骤：

***Step1.***通过取出序列最后一个元素得到二叉搜索树的根节点；

***Step2.***在二叉搜索树中左子树的结点小于根结点，因此可以遍历一次得到左子树；

***Step3.***在二叉搜索树中右子树的结点大于根结点，因此可以继续遍历后序元素得到右子树；

***Step4.***重复以上步骤递归判断左右子树是不是二叉搜索树，如果都是，则返回true，如果不是，则返回false;

## 2.2 代码实现 ##

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.1 测试用例 ##

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

## 3.2 测试结果 ##

![381412-20150903232632356-248041995.png][]

作者：[周旭龙][Link 1]

出处：[http://edisonchou.cnblogs.com][http_edisonchou.cnblogs.com]

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接。

转载于:https://www.cnblogs.com/edisonchou/p/4780973.html

[381412-20150903221345825-2126716036.jpg]: /images/20211122/b3e31513289d4a65976340d57a9755a1.png
[381412-20150903232632356-248041995.png]: /images/20211122/8aff573e50f944dab566bb137a365f93.png
[Link 1]: http://www.edisonchou.cn
[http_edisonchou.cnblogs.com]: http://edisonchou.cnblogs.com