二叉搜索树的后序遍历序列

简介: 题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:          8       /  \      6    10    / \    / \   5   7   9  11 因此返回true。

 

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。

例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:

         8
       /  \
      6    10
    / \    / \
   5   7   9  11

因此返回true。

如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。

分析:这是一道trilogy的笔试题,主要考查对二元查找树的理解。

在后续遍历得到的序列中,最后一个元素为树的根结点。从头开始扫描这个序列,比根结点小的元素都应该位于序列的左半部分;从第一个大于根结点开始到根结点前 面的一个元素为止,所有元素都应该大于根结点,因为这部分元素对应的是树的右子树。根据这样的划分,把序列划分为左右两部分,我们递归地确认序列的左、右 两部分是不是都是二元查找树。

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

 参考代码:

using namespace std;

///////////////////////////////////////////////////////////////////////
// Verify whether a squence of integers are the post order traversal
// of a binary search tree (BST)
// Input: squence - the squence of integers
//        length  - the length of squence
// Return: return ture if the squence is traversal result of a BST,
//         otherwise, return false
///////////////////////////////////////////////////////////////////////
bool verifySquenceOfBST(int squence[], int length)
{
      if(squence == NULL || length <= 0)
            return false;

      // root of a BST is at the end of post order traversal squence
      int root = squence[length - 1];

      // the nodes in left sub-tree are less than the root
      int i = 0;
      for(; i < length - 1; ++ i)
      {
            if(squence[i] > root)
                  break;
      }

      // the nodes in the right sub-tree are greater than the root
      int j = i;
      for(; j < length - 1; ++ j)
      {
            if(squence[j] < root)
                  return false;
      }

      // verify whether the left sub-tree is a BST
      bool left = true;
      if(i > 0)
            left = verifySquenceOfBST(squence, i);

      // verify whether the right sub-tree is a BST
      bool right = true;
      if(i < length - 1)
            right = verifySquenceOfBST(squence + i, length - i - 1);

      return (left && right);
}

 

img_e00999465d1c2c1b02df587a3ec9c13d.jpg
微信公众号: 猿人谷
如果您认为阅读这篇博客让您有些收获,不妨点击一下右下角的【推荐】
如果您希望与我交流互动,欢迎关注微信公众号
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。

目录
相关文章
|
8月前
|
Java C++ 索引
leetcode-106:从中序与后序遍历序列构造二叉树
leetcode-106:从中序与后序遍历序列构造二叉树
60 0
|
3月前
|
存储 索引 Python
从中序与后序遍历序列构造二叉树
【10月更文挑战第13天】这段内容介绍了一种基于中序和后序遍历序列构建二叉树的方法。通过识别后序遍历中的根节点,并利用中序遍历划分左右子树,进而递归构建整棵树。文中提供了具体示例及Python代码实现,并分析了该方法的时间与空间复杂度。
139 0
21_从中序与后序遍历序列构造二叉树
21_从中序与后序遍历序列构造二叉树
|
C++ 索引
从中序与后序遍历序列构造二叉树(C++实现)
从中序与后序遍历序列构造二叉树(C++实现)
91 1
【剑指offer】-二叉搜索树的后序遍历序列-23/67
【剑指offer】-二叉搜索树的后序遍历序列-23/67
剑指offer 34. 二叉搜索树的后序遍历序列
剑指offer 34. 二叉搜索树的后序遍历序列
58 0
|
机器学习/深度学习
每日三题-对称二叉树、从前序与中序遍历序列构造二叉树、不同的二叉搜索树
每日三题 对称二叉树 从前序与中序遍历序列构造二叉树 不同的二叉搜索树
103 4
每日三题-对称二叉树、从前序与中序遍历序列构造二叉树、不同的二叉搜索树
|
算法 前端开发 程序员
二叉树的后序遍历序列
二叉树的后序遍历序列
二叉树的后序遍历序列

热门文章

最新文章