问题描述:
判断整数序列是不是二元查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
import java.util.Arrays;
public class Judge {
public static boolean judge(int[] Data){
int len = Data.length;
int root = Data[len-1];
int small = -1;
int large = -1;
for(int i=0;i<len; i++){
if(Data[i]>root){
large = i;
}
if(Data[i]<root){
small = i;
}
}
if(small>large){
return false;
}else if(small==-1&&large==-1){
return true;
}
else{
printArray(Data);
System.out.println("Small:"+small+",Lrge:"+large);
int[] smallPart = null;
int[] bigPart = null;
if(small!=-1){
smallPart = new int[small+1];
smallPart = Arrays.copyOfRange(Data, 0, small+1);
}
if(large!=-1){
bigPart = new int[large-small+1];
bigPart = Arrays.copyOfRange(Data, small+1, large+1);
}
if(small==-1){
return judge(bigPart);
}else if(large==-1){
return judge(smallPart);
}else
return judge(smallPart)&&judge(bigPart);
}
}
public static void printArray(int[] data){
for(int i=0; i<data.length; i++){
System.out.print(data[i]+" ");
}
System.out.println();
}
public static void main(String[] args){
int[] data = {5,7,6,9,11,10,8};
System.out.println(judge(data));
}
}
分享到:
相关推荐
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果. 8 / \ 6 10 / \ / \ 5...
9. 判断整数序列是不是二元查找树的后序遍历结果:本题目考察了二元查找树和算法的知识,要求判断整数序列是不是二元查找树的后序遍历结果。解决方法是使用递归算法,判断序列是否满足二元查找树的性质。
判断整数序列是不是二元查找树的后序遍历结果 **题目描述**: 给定一个整数序列,判断该序列是否是二元查找树的后序遍历结果。 **解题思路**: - 二元查找树的后序遍历结果的最后一个元素是根节点。 - 二元查找树...
**八、判断整数序列是不是二元查找树的后序遍历结果** 判断一个整数序列是否为二元查找树的后序遍历结果,关键在于理解二元查找树的性质。后序遍历的结果中,最后一个元素一定是根节点的值。根据二元查找树的特性,...
9. **整数序列是否为二元查找树后序遍历**: 后序遍历的顺序是左子树、右子树、根节点。通过检查序列是否满足这一性质,可以判断给定序列是否是二元查找树的后序遍历结果。 以上就是根据题目内容涉及的一些算法和...
判断一个整数序列是否为二元查找树的后序遍历结果,需要验证序列是否满足后序遍历的特点(左-右-根),并且每个子树的根节点值应该大于其左子树的所有节点值,小于右子树的所有节点值。 其他面试题涉及的知识点包括...
6. **判断序列是否为二元查找树后序遍历**:检查一个整数序列是否为二元查找树的后序遍历结果。二元查找树的后序遍历特点是左子树-右子树-根节点,需要考虑递归关系。 7. **翻转单词顺序**:在句子中翻转单词的顺序...
9. **判断整数序列是否为二元查找树的后序遍历结果**: 判断给定序列是否符合二叉查找树后序遍历的特点,通常后序遍历的顺序是左子树-右子树-根节点,可以用递归或栈来检查这个顺序。 以上就是这些算法面试题的...
判断整数序列是不是二元查找树的后序遍历结果 **知识点概述:** 本题要求判断给定的整数序列是否为某二元查找树的后序遍历结果。 **解题思路:** 1. **二叉搜索树的性质:**二叉搜索树的后序遍历序列具有一定的...
判断整数序列是否为二元查找树的后序遍历结果,可以利用后序遍历的性质:左子树遍历完后遍历右子树,最后遍历根节点。遍历过程中,检查当前节点值是否小于或等于其前一个节点值,如果不是,则序列不是二元查找树的...
8. 判断整数序列是否是二元查找树的后序遍历结果:二元查找树的后序遍历结果有其特性,根据这些特性可以递归或迭代地验证给定序列是否符合。 9. 查找最小的K个元素:利用最大堆的数据结构可以高效地找出一组数中的...
9. **判断整数序列是否为二元查找树的后序遍历**: 后序遍历的顺序是左子树-右子树-根节点。可以使用动态规划的方法,检查当前节点是否满足后序遍历规则,以及它的左右子序列是否合法。 以上题目涉及的主要知识点...
判断整数序列是不是二元查找树的后序遍历结果 **知识点:** - **后序遍历**:按照左-右-根的顺序遍历二叉树。 **解决思路:** - 二元查找树的后序遍历结果中,最后一个元素为根节点。 - 从最后一个元素往前遍历,...
9. **判断整数序列是否为二元查找树的后序遍历结果**: - 后序遍历的顺序是左子树、右子树、根节点。可以构建二叉树并检查序列是否满足后序遍历的性质,即对于任意子序列,左子序列 根节点,右子序列 > 根节点。 ...
8. 判断整数序列是否为二元查找树的后序遍历结果: 这个问题考察了对于二元查找树遍历的理解,需要根据后序遍历的特性来重构树并验证序列。 9. 查找最小的K个元素: 使用最大堆可以有效地找到最小的K个元素。堆是...
#### 2.8 判断整数序列是不是二元查找树的后序遍历结果 - **问题描述**:给定一个整数序列,判断这个序列是否可能是一棵二元查找树的后序遍历结果。 - **解决方案**: - 后序遍历的最后一个元素是根节点的值。 - ...
判断整数序列是不是二元查找树的后序遍历结果 题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一整数序列是...