`

判断整数序列是不是二元查找树的后序遍历结果

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

   6   10

  / \   / \

5 7  9 11
因此返回true。


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

关键字: 1.二元查找树 : 二元查找树的特点 第一:左边节点小于右边节点 第一推论:因为中序遍历是先遍历左边再遍历右边,意味着中序遍历是有序的、
2.后序遍历:后续遍历的特点是:先左节点,再右节点,再根节点,所以可以知道后序遍历的最后一个元素是根元素。

我们用分治思想来做:
(a[0]...a[i]) < a[n] < (a[i+1]...a[n-1])
...
a[0]<a[3]<a[1]


public static boolean verifyOfBST(int data[], int begin, int end) {
  if (data == null || begin > end)
   return false;
  if (begin == end) {
   return true;
  }
  int root = data[end];
  for (int i = begin; i < end; ++i) {//寻找i,保证左边都小于a[n]
   if (data[i] > root)
    break;
  }
  // the nodes in the right sub-tree are greater than the root
  for (int j = i; j < end; ++j) { //验证右边都大于a[n]
   if (data[j] < root)
    return false;
  }
  // verify whether the left sub-tree is a BST
  boolean left = true;
  if (i > 0)
   left = verifyOfBST(data, begin, i - 1);

  // verify whether the right sub-tree is a BST
  boolean right = true;
  if (i < end)
   right = verifyOfBST(data, i, end - 1);

  return (left && right);

}



分享到:
评论

相关推荐

    判断整数序列是否为二元查找树的后序遍历结果的解决方法

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

    算法面试题总结_嵌入式-常用知识&面试题库_大厂面试真题.doc

    9. 判断整数序列是不是二元查找树的后序遍历结果:本题目考察了二元查找树和算法的知识,要求判断整数序列是不是二元查找树的后序遍历结果。解决方法是使用递归算法,判断序列是否满足二元查找树的性质。

    100 questions by_july

    判断整数序列是不是二元查找树的后序遍历结果 **题目描述**: 给定一个整数序列,判断该序列是否是二元查找树的后序遍历结果。 **解题思路**: - 二元查找树的后序遍历结果的最后一个元素是根节点。 - 二元查找树...

    数据结构C问题

    **八、判断整数序列是不是二元查找树的后序遍历结果** 判断一个整数序列是否为二元查找树的后序遍历结果,关键在于理解二元查找树的性质。后序遍历的结果中,最后一个元素一定是根节点的值。根据二元查找树的特性,...

    常见:算法面试题总结 (2)1

    9. **整数序列是否为二元查找树后序遍历**: 后序遍历的顺序是左子树、右子树、根节点。通过检查序列是否满足这一性质,可以判断给定序列是否是二元查找树的后序遍历结果。 以上就是根据题目内容涉及的一些算法和...

    【史上最全】算法面试题集锦.pdf

    判断一个整数序列是否为二元查找树的后序遍历结果,需要验证序列是否满足后序遍历的特点(左-右-根),并且每个子树的根节点值应该大于其左子树的所有节点值,小于右子树的所有节点值。 其他面试题涉及的知识点包括...

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

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

    常见:算法面试题21

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

    微软面试题库

    判断整数序列是不是二元查找树的后序遍历结果 **知识点概述:** 本题要求判断给定的整数序列是否为某二元查找树的后序遍历结果。 **解题思路:** 1. **二叉搜索树的性质:**二叉搜索树的后序遍历序列具有一定的...

    经典算法面试题

    判断整数序列是否为二元查找树的后序遍历结果,可以利用后序遍历的性质:左子树遍历完后遍历右子树,最后遍历根节点。遍历过程中,检查当前节点值是否小于或等于其前一个节点值,如果不是,则序列不是二元查找树的...

    c和c++500强面试题

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

    Google等公司数据结构+算法面试.pdf

    9. **判断整数序列是否为二元查找树的后序遍历**: 后序遍历的顺序是左子树-右子树-根节点。可以使用动态规划的方法,检查当前节点是否满足后序遍历规则,以及它的左右子序列是否合法。 以上题目涉及的主要知识点...

    微软等公司的面试题

    判断整数序列是不是二元查找树的后序遍历结果 **知识点:** - **后序遍历**:按照左-右-根的顺序遍历二叉树。 **解决思路:** - 二元查找树的后序遍历结果中,最后一个元素为根节点。 - 从最后一个元素往前遍历,...

    常见:算法面试题总结1

    9. **判断整数序列是否为二元查找树的后序遍历结果**: - 后序遍历的顺序是左子树、右子树、根节点。可以构建二叉树并检查序列是否满足后序遍历的性质,即对于任意子序列,左子序列 根节点,右子序列 &gt; 根节点。 ...

    刀疤鸭之数据结构面试题

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

    C语言面试题总结汇总经典.pdf

    #### 2.8 判断整数序列是不是二元查找树的后序遍历结果 - **问题描述**:给定一个整数序列,判断这个序列是否可能是一棵二元查找树的后序遍历结果。 - **解决方案**: - 后序遍历的最后一个元素是根节点的值。 - ...

    脑力保健 微软,GOOGLE等试题试做 C#版

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

Global site tag (gtag.js) - Google Analytics