文档章节

【九度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
海淀
程序员
数据结构与算法(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
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
06/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

阿里云API网关使用教程

API 网关(API Gateway)提供高性能、高可用的 API 托管服务,帮助用户对外开放其部署在 ECS、容器服务等阿里云产品上的应用,提供完整的 API 发布、管理、维护生命周期管理。用户只需进行简...

mcy0425
30分钟前
4
0
解决远程登陆误按ctrl+s锁屏假死恢复

使用putty时,偶尔发生屏幕假死,不能输入等情况。 后来发现,只要数据ctrl+s,就会假死;输入ctrl+q就可以恢复过来。 很多刚从windows转移到linux上来工作的朋友,在用vi/vim编辑文件时,常常...

HJCui
33分钟前
0
0
@Transactional

事务管理是应用系统开发中必不可少的一部分。Spring 为事务管理提供了丰富的功能支持。Spring 事务管理分为编程式和声明式的两种方式。编程式事务指的是通过编码方式实现事务;声明式事务基于...

asdf08442a
38分钟前
2
0
widows下强制解除8080端口占用问题

使用win+R打开命令窗口 输入以下命令查看哪个任务占用了8080端口 netstat -ano |findstr "8080" 然后通过任务id强制关闭占用该端口的进程 tskill 10044 // 自己的试情况而定,这个ID是LISTE...

_Artisan
47分钟前
2
0
productFlavors简单实用

最近项目中,不同环境需要配置的参数越来越多,为了减少修改代码次数。研究了一下productFlavors的使用方式,总结如下 1. as3.0以上版本使用productFlavors时需要指定一个flavorDimensions,...

火云
49分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部