首页 > 剑指offer > 面试题精选100题(06)-二叉查找树的后序遍历结果[数据结构]
2013
12-13

面试题精选100题(06)-二叉查找树的后序遍历结果[数据结构]

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回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);
}

转自:http://zhedahht.blog.163.com/


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.