文档章节

【九度OJ1367】|【剑指offer24】二叉搜索树的后序遍历序列

aqia358
 aqia358
发布于 2013/12/03 11:04
字数 454
阅读 36
收藏 0

题目描述:

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

输入:

每个测试案例包括2行:

第一行为1个整数n(1<=n<=10000),表示数组的长度。

第二行包含n个整数,表示这个数组,数组中的数的范围是[0,100000000]。

输出:

对应每个测试案例,如果输入数组是某二叉搜索树的后序遍历的结果输出Yes,否则输出No。

样例输入:
7
5 7 6 9 11 10 8
4
7 4 6 5
样例输出:
Yes
No


解:二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树
    后序遍历则最后一个元素为根元素

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
 
public class Main {
 
    public static boolean isBST(int[] array, int begin, int end) {
        int left = begin;
        int right = end - 1;
        if(end - begin <= 1)
            return true;
        while (left < end && array[end] > array[left])
            left++;
        while (right > begin && array[end] < array[right])
            right--;
        if(left - 1 == right || left == right)
            return isBST(array, begin, left - 1) && isBST(array, left, end - 1);
        else
            return false;
    }
 
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        while (st.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) st.nval;
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                st.nextToken();
                a[i] = (int) st.nval;
            }
            if (Main.isBST(a, 0, n - 1))
                System.out.println("Yes");
            else
                System.out.println("No");
        }
    }
 
}
 
/**************************************************************
    Problem: 1367
    User: aqia358
    Language: Java
    Result: Accepted
    Time:370 ms
    Memory:24264 kb
****************************************************************/






© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
数据结构与算法(3)——树(二叉、二叉搜索树)

前言:题图无关,现在开始来学习学习树相关的知识 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列(https://www.ji...

我没有三颗心脏
07/11
0
0
[剑指offer] 二叉搜索树的后序遍历序列

题目描述 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 解题思路 二叉搜索树: 左子树

繁著
07/01
0
0
【算法系列 五】 树和图

二叉搜索树的后序遍历序列(九度1367) 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 与此题相...

Hosee
2016/08/08
173
0
24. 二叉搜索树的后序遍历序列

题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。 思路:因为是二叉搜索树,所以每个根...

无精疯
04/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Qt那些事0.0.7

在帮助文档(Overview - QML and C++ Integration)中随缘遇到一张图,是关于C++对象与QML整合介绍的,值得标记下来,虽然大部分功能也有所涉猎,但是还是留个记号,万一哪天我失忆了还想写Q...

Ev4n
18分钟前
0
0
快速幂运算

题:求一个数 data 的 n 次幂,要求时间复杂度为log(n) 1:递归算法: /** * x^3=(x^2)*x;x^7=(x^3)^2 * x * * 递归算法 * @param data 底数 * @param n 次...

偶尔诗文
23分钟前
1
0
Google 宣布将会关闭消费者版本 Google+

Google 家的社交平台 Google+ 原来曾经在今年 3 月发生了一次严重的用户资料外泄事故,但这科网巨擘却一直保密,直至今天华尔街日报把事件披露之后才确认事件。Google 在重申问题已经即时解决...

问题终结者
36分钟前
1
0
腾讯三大运维开源项目齐聚“OSCAR开源先锋日”

10月20日,腾讯开源三大运维开源项目——TARS、蓝鲸和织云Metis首次集结,参与了由中国信息通信研究院主办、云计算标准与开源推进委员会承办的 “OSCAR开源先锋日”。会上,腾讯开源团队与前...

腾讯开源
41分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部