文档章节

【九度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
剑指offer 24. 二叉搜索树的后序遍历序列

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

dby_freedom
11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

以太坊PHP离线交易开发包

EthTool开发包适用于希望采用裸交易的PHP以太坊应用开发,主要包含以下特性: 支持裸交易部署/调用合约 内置etherscan和infura支持 keystore生成与读取,兼容geth/parity 采用裸交易的一个好...

笔阁
20分钟前
0
0
SRE的含义及与 DevOps 如何关联?

虽然站点可靠性工程师(site reliability engineer SRE)角色在近几年变得流行起来,但是很多人 —— 甚至是软件行业里的 —— 还不知道 SRE 是什么或者 SRE 都干些什么。为了搞清楚这些问题...

linuxCool
21分钟前
1
0
月入3万之一个程序员的转行坎坷历程

陈年往事 “我月入3万,怎么会少少了你一个鸡蛋啊?” 这是2017年9月左右的一个新闻,一位煎饼摊大妈因和顾客争执时脱口而出这样一句话而走红。当时还上了各大新闻的头条。 互联网兴起今天,...

苏南-首席填坑官
43分钟前
2
1
OSChina 周一乱弹 —— 眼看着这颗陨石砸了下来

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子:分享Nachtblut的单曲《Antik》 《Antik》- Nachtblut 手机党少年们想听歌,请使劲儿戳(这里) @mr_chip :上海的初雪之后有点冷 ...

小小编辑
今天
394
7
Confluence 6 修改导航显示选项

选择 子页面(Child pages)来在边栏中查看当前页面的子页面。 选择 页面树(Page tree)来查看整个空间的页面树,扩展当前的页面。 你也可以选择是否完全隐藏导航显示选项或者添加你希望可见...

honeymose
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部