文档章节

验证给定序列是否是BST的preoder序列

B
 BlueWoods
发布于 2015/08/27 21:17
字数 475
阅读 1456
收藏 1

from leetcode https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/

比如序列 2, 1, 3 是如下图的BST的preorder 序列:

但是2, 3, 1就不会是一个preorder序列;

先复习一下BST,给定一个节点,其左子树的所有节点都小于该节点,右子树的所有节点都大于该节点;preorder序列是指在遍历该BST的时候,先记录根节点,再遍历左子树,然后遍历右子树;所以一个preorder序列有这样一个特点,左子树的序列必定都在右子树的序列之前;并且左子树的序列必定都小于根节点,右子树的序列都大于根节点;

根据上面的特点很容易通过递归的方式完成:

  1. 如果序列只有一个元素,那么肯定是正确的,对应只有一个节点的树;

  2. 如果多于一个元素,以当前节点为根节点;并从当前节点向后遍历,直到大于根节点的节点出现(或者到尾巴),那么根节点之后,该大节点之前的,是左子树;该大节点及之后的组成右子树;递归判断左右子树即可;

  3. 那么什么时候一个序列肯定不是一个preorder序列呢?前面得到的右子树,如果在其中出现了比根节点还小的数,那么就可以直接返回false了;

代码如下:

public boolean verifyPreorder(int[] preorder) {
    return verifyPreorder(preorder, 0, preorder.length);
}

public boolean verifyPreorder(int[] seq, int start, int end) {
    if (start + 1 >= end) {
        return true;
    }

    int root = seq[start];

    int i = start + 1;
    while (i < end && seq[i] < root) {
        i++;
    }

    if (i < end) {
        int j = i;
        while (j < end && seq[j] > root) {
            j++;
        }
        if (j < end) {
            return false;
        }

        return verifyPreorder(seq, start + 1, i) && verifyPreorder(seq, i, end);
    } else {
        return verifyPreorder(seq, start + 1, end);
    }
}


© 著作权归作者所有

B
粉丝 4
博文 39
码字总数 21286
作品 0
杭州
私信 提问
PAT A1043. Is It a Binary Search Tree (25)

Is It a Binary Search Tree (25) https://www.patest.cn/contests/pat-a-practise/1043 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue A Bina......

阿豪boy
2017/03/11
11
0
验证二叉搜索树

原题   Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:   The left subtree of a node contains only nodes with k......

一贱书生
2016/12/20
8
0
二叉查找树的实现与讲解(C++)

注:这篇文章源于:https://mp.csdn.net/postedit/99710904, 无需怀疑抄袭,同一个作者,这是我在博客园的账号。 在二叉树中,有两种非常重要的条件,分别是两类数据结构的基础性质。 其一是...

Brower
08/19
0
0
LeetCode算法题-Search in a Binary Search Tree(Java实现)

这是悦乐书的第295次更新,第314篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第163题(顺位题号是700)。给定一个二叉搜索树(BST)的和正整数val。 你需要在BST中找到节点...

小川94
04/02
0
0
[LeetCode] Serialize and Deserialize BST 二叉搜索树的序列化和去序列化

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a networ......

机器的心脏
2017/12/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

golang-字符串-地址分析

demo package mainimport "fmt"func main() {str := "map.baidu.com"fmt.Println(&str, str)str = str[0:5]fmt.Println(&str, str)str = "abc"fmt.Println(&s......

李琼涛
今天
4
0
Spring Boot WebFlux 增删改查完整实战 demo

03:WebFlux Web CRUD 实践 前言 上一篇基于功能性端点去创建一个简单服务,实现了 Hello 。这一篇用 Spring Boot WebFlux 的注解控制层技术创建一个 CRUD WebFlux 应用,让开发更方便。这里...

泥瓦匠BYSocket
今天
6
0
从0开始学FreeRTOS-(列表与列表项)-3

FreeRTOS列表&列表项的源码解读 第一次看列表与列表项的时候,感觉很像是链表,虽然我自己的链表也不太会,但是就是感觉很像。 在FreeRTOS中,列表与列表项使用得非常多,是FreeRTOS的一个数...

杰杰1号
今天
8
0
Java反射

Java 反射 反射是框架设计的灵魂(使用的前提条件:必须先得到代表的字节码的 Class,Class 类 用于表示.class 文件(字节码)) 一、反射的概述 定义:JAVA 反射机制是在运行状态中,对于任...

zzz1122334
今天
6
0
聊聊nacos的LocalConfigInfoProcessor

序 本文主要研究一下nacos的LocalConfigInfoProcessor LocalConfigInfoProcessor nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/impl/LocalConfigInfoProcessor.java p......

go4it
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部