题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
package cn.emma.interview_9;
public class Ex9 {
public static boolean isBackOrder(int[] a,int left,int right){
int root = a[right];
if(left < right){
int i=left,j=right-1;
while(a[i] < root){
i++;
}
while(a[j] > root){
j--;
}
if(i != j +1){
return false;
}else{
return isBackOrder(a, left, j) && isBackOrder(a, i, right-1);
}
}
return true;
}
public static void main(String[] args) {
int[] a = {5,7,6,9,11,10,8};
System.out.println(isBackOrder(a, 0, a.length-1));
}
}
分享到:
相关推荐
本微软面试100题系列,共计11篇文章,300多道面试题,截取本blog索引性文章:程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大系列集锦:http://blog.csdn.net/v_july_v/article/details/6543438,中的第一部分...
微软面试100题系列,面试专用,共11篇文章,300道面试题,包含国内BAT面试题
ms100(微软面试100题)答案整理版
微软面试100题完整版(题目答案齐全) 微软面试100题完整版(题目答案齐全) 微软面试100题完整版(题目答案齐全) 微软面试100题完整版(题目答案齐全)
微软试题合集,里面是一些微软的面试题。希望对找工作的人有帮助
微软面试100题(含参考答案)
本微软面试100题系列,共计11篇文章,300多道面试题,祝大家都能找到令自己满意的工作
面试题 经典面试题 微软面试题 C#面试面试题 经典面试题 微软面试题 C#面试
本微软面试100题系列,共计11篇文章,300多道面试题,截取本blog索引性文章:程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大系列集锦:http://blog.csdn.net/v_july_v/article/details/6543438,中的第一部分...
网友yui评论,真是够多的了,从此,不用再看其它面试题.... 一句话,请享用。 July、2010/11.05. ----------------------------------------------- 其它资源,下载地址: [最新整理公布][汇总II]微软等数据结构+...
微软等100+公司数据结构与算法面试题 面试复习专用
July出品,必出精品。本文整理了微软面试常出的100道算法题,并附上详细的源码解答,全部是干货。
面试_微软面试100题全部答案.docx
微软公司等数据结构+算法面试100题(第1-100题)全部出炉
微软等公司数据结构+算法面试100题之第41-60题答案 --- 答案V0.4版 My Blog:http://blog.csdn.net/v_JULY_v 微软等100题系列,整理资源下载地址:题目系列: 1.[最新整理公布][汇总II]微软等数据结构+算法面试100...
微软等公司面试数据结构或算法的经典100题,还有答案集锦
微软面试100题 doc版
微软面试试题...微软面试试题微软面试试题微软面试试题