`

程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果

阅读更多

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
          8
        /   \
       6     10
     / \     / \
    5    7    9   11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
分析:这是一道trilogy的笔试题,主要考查对二元查找树的理解。
在后续遍历得到的序列中,最后一个元素为树的根结点。从头开始扫描这个序列,比根结点小的元素都应该位于序列的左半部分;从第一个大于跟结点开始到跟结点前面的一个元素为止,所有元素都应该大于跟结点,因为这部分元素对应的是树的右子树。根据这样的划分,把序列划分为左右两部分,我们递归地确认序列的左、右两部分是不是都是二元查找树。
参考代码:

C++代码 复制代码
  1. using namespace std;   
  2. ///////////////////////////////////////////////////////////////////////   
  3. // Verify whether a squence of integers are the post order traversal   
  4. // of a binary search tree (BST)   
  5. // Input: squence - the squence of integers   
  6. //         length   - the length of squence   
  7. // Return: return ture if the squence is traversal result of a BST,   
  8. //          otherwise, return false   
  9. ///////////////////////////////////////////////////////////////////////   
  10. bool verifySquenceOfBST(int squence[], int length)   
  11. {   
  12.       if(squence == NULL || length <= 0)   
  13.             return false;   
  14.       // root of a BST is at the end of post order traversal squence   
  15.       int root = squence[length - 1];   
  16.       // the nodes in left sub-tree are less than the root   
  17.       int i = 0;   
  18.       for(; i < length - 1; ++ i)   
  19.        {   
  20.             if(squence > root)   
  21.                   break;   
  22.        }   
  23.   
  24.       // the nodes in the right sub-tree are greater than the root   
  25.       int j = i;   
  26.       for(; j < length - 1; ++ j)   
  27.        {   
  28.             if(squence[j] < root)   
  29.                   return false;   
  30.        }   
  31.   
  32.       // verify whether the left sub-tree is a BST   
  33.       bool left = true;   
  34.       if(i > 0)   
  35.              left = verifySquenceOfBST(squence, i);   
  36.   
  37.       // verify whether the right sub-tree is a BST   
  38.       bool right = true;   
  39.       if(i < length - 1)   
  40.              right = verifySquenceOfBST(squence + i, length - i - 1);   
  41.   
  42.       return (left && right);  
分享到:
评论

相关推荐

    程序员面试题精选100题(经典!)

    递归遍历分为前序遍历、中序遍历和后序遍历,本题使用的是中序遍历,因为中序遍历的结果正好是按照节点值排序的序列。 4. 指针操作: 在C/C++等语言中,指针是核心概念之一,涉及到内存地址的操作。在将二元查找树...

    程序员面试题精选100题.doc

    中序遍历是二元查找树的一种遍历策略,通常用于打印或显示树的有序序列。对于非空树,中序遍历的顺序是:首先遍历左子树,然后访问根节点,最后遍历右子树。 3. **双向链表(Doubly Linked List)** 双向链表是一...

    程序员面试100题数据结构和算法

    6. **判断序列是否为二元查找树后序遍历**:检查一个整数序列是否为二元查找树的后序遍历结果。二元查找树的后序遍历特点是左子树-右子树-根节点,需要考虑递归关系。 7. **翻转单词顺序**:在句子中翻转单词的顺序...

    程序员面试题精选

    在程序员面试中,经常会遇到与数据结构和算法相关的题目,特别是与树相关的题目,例如将二元查找树转换成排序的双向链表。这个问题主要考察的是对二元查找树特性的理解以及递归或迭代算法的运用。 二元查找树...

    程序员面试题精选100题.pdf

    这里我们重点讨论的是如何将一个二元查找树(Binary Search Tree, BST)转换成一个排序的双向链表,这是一个典型的面试题,考察了对数据结构的理解和递归算法的应用。 二元查找树是一种特殊的二叉树,每个节点的值...

    程序员面试题精选100题完整版.pdf,这是一份不错的文件

    中序遍历二元查找树的顺序是:左子树 -&gt; 节点 -&gt; 右子树,对于排序树来说,中序遍历的结果是一个升序序列。 6. 结构体(Struct): 在C/C++中,结构体用于封装多个不同类型的数据,如BSTreeNode结构体封装了节点...

    程序员面试题精选解答

    - 二元查找树的中序遍历结果是升序序列。 - 由于二元查找树具有上述性质,因此非常适合用来实现有序集合或符号表等数据结构。 - **应用:** - 数据库索引构建。 - 文件系统的目录结构管理。 - 缓存机制中的键值...

    常见:程序员面试题精选100题1

    - 中序遍历二元查找树会得到一个有序序列,因为这是二元查找树的性质。 - 每遍历到一个节点,就将其添加到当前已形成的链表尾部。 4. **递归实现**: 在这两种策略中,递归是关键。对于思路一,递归调用`...

    程序员面试题精选100题

    【程序员面试题精选100题】是一份中文Word文档,包含了针对程序员的100道面试题目,这些题目详细解答了如何准备编程面试,尤其是技术面试环节。面试是求职过程中至关重要的一环,它能让雇主直接评估应聘者的技能和...

    程序员面试题精选100题目

    在程序员面试中,掌握各种算法和数据结构是至关重要的,尤其是对于二元查找树(BST)的处理。本题目的核心是将一棵二元查找树转化为一个排序的双向链表,而无需创建新的节点,仅通过调整节点间的指针实现。这种转换...

    程序员面试100题

    对于二元查找树,中序遍历的结果是一个升序序列。因此,我们可以遍历整棵树,每次访问一个节点时,将其添加到已排序的链表尾部,这样遍历结束后,整个树就变成了一个有序链表。 6. **代码实现** 在提供的代码中,`...

    常见:算法面试题21

    9. **判断整数序列是否为二元查找树的后序遍历结果**: 判断给定序列是否符合二叉查找树后序遍历的特点,通常后序遍历的顺序是左子树-右子树-根节点,可以用递归或栈来检查这个顺序。 以上就是这些算法面试题的...

    刀疤鸭之数据结构面试题

    8. 判断整数序列是否为二元查找树的后序遍历结果: 这个问题考察了对于二元查找树遍历的理解,需要根据后序遍历的特性来重构树并验证序列。 9. 查找最小的K个元素: 使用最大堆可以有效地找到最小的K个元素。堆是...

    c和c++500强面试题

    8. 判断整数序列是否是二元查找树的后序遍历结果:二元查找树的后序遍历结果有其特性,根据这些特性可以递归或迭代地验证给定序列是否符合。 9. 查找最小的K个元素:利用最大堆的数据结构可以高效地找出一组数中的...

    程序员面试精选 主要是数据结构和算法

    二元查找树的中序遍历顺序会得到一个升序序列,因此我们可以采用中序遍历的方式,依次将遍历到的节点加入到已有的链表中,形成一个排序的双向链表。 **参考代码**(思路一): ```cpp struct BSTreeNode { int m_...

    2011年程序员面试试题宝典100题_附程序

    在《2011年程序员面试试题宝典100题》中,有一道经典的算法题:“把二元查找树转变成排序的双向链表”。这道题目考察了程序员对数据结构和算法的理解深度,尤其是对于树形结构与链表之间的转换能力。 #### 题目解析...

Global site tag (gtag.js) - Google Analytics