[剑指offer]二叉搜索树的后序遍历数列

[剑指offer]二叉搜索树的后序遍历数列

剑指offer-二叉搜索树的后序遍历序列

题目描述

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

参考以下这颗二叉搜索树:

     5
    / \
   2   6
  / \
 1   

示例 1:
输入: [1,6,3,2,5]
输出: false

示例 2:
输入: [1,3,2,6,5]
输出: true

提示:
数组长度 <= 1000

解题思路
  • 二叉搜索树特点:若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值;若它的右子树不为空,则右子树上所有节点的值均大于它的根节点的值。
  • 后序遍历序列的最后一个值为二叉树的根节点,前面分为两部分,前半部分都小于根节点的值,后半部分都大于根节点的值。
  • 假设后序遍历序列长度为len,最后一个值为root,找出序列中第一个大于root的值的位置i,那么[0,i)为它的左子树,[i,len)为它的右子树。
实现代码
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int len = postorder.size();
        if(len==0)
            return true;
            
        int root = postorder[len-1];//根节点的值
        vector<int> left;
        vector<int> right;
        int temp=0;
        
        for(int i=0;i<len-1;i++){//得到左子树序列
            temp=i;//保存第一个大于root值的位置
            if(postorder[i]<root)
                left.push_back(postorder[i]);//左子树
            else//找到了第一个大于root的值,temp保存了它的位置                
                break;                        
        }
        
        if(temp==len-2)//说明左边的值都小于root,没有右子树
            temp=temp+1;
            
        for(int i=temp;i<len-1;i++){//得到右子树序列
            if(postorder[i]<root)//如果[temp,len-1)中有小于root值得,返回flase
                return false;
            right.push_back(postorder[i]);//右子树
        }
        
        if(verifyPostorder(left)&verifyPostorder(right))//递归,判断左子树和右子树是否都符合二叉搜索树条件
            return true;
            
        return false;
    }
};

热门文章

暂无图片
编程学习 ·

Python3 元类编程

在Python中一切接对象,类也是一个对象,所有的类都是有type类创建,我们实际开发中最常用的type方法,是用来获取某个对象的类型的,例如type(1) ⇒ int 、type(‘str’) ⇒ str。但是type还有一种用法,就是用来创建类的。 1、通过type动态创建无父类、无属性的类 People = t…
暂无图片
编程学习 ·

RFID资产管理解决方案-RFID固定资产管理-新导智能

RFID资产管理解决方案系统集成了技能含量很高的远间隔无线射频辨认技能、短间隔射频技能及多用户防抵触技能监测技能,标签、定位器、读写器、通讯网关等,选用全新的嵌入式微处理器和嵌入式软件进行规划,体系信号穿透力强,对人体无电磁污染、环境适应性强,可一起定位多个标…
暂无图片
编程学习 ·

基于jupyter notebook的python编程-----Win10通过OpenCv-3.4.1进行人脸口罩数据集的模型训练并进行戴口罩识别检测

基于jupyter notebook的python编程-----Win10通过OpenCv-3.4.1进行人脸口罩数据集的模型训练并进行戴口罩识别检测目录一、OpenCv的下载及安装1、OpenCv的下载2、OpenCv的安装3、查看是否具有模型训练环境二、人脸口罩数据集的下载及处理1、人脸口罩数据集下载2、数据集重命名为…
暂无图片
编程学习 ·

深度学习入门教程-1.1 神经网络是什么

到底什么是人工神经网络?前面提到,人工神经网络是从大脑的理解中汲取灵感而形成的。在我们的大脑中,有数十亿个神经元,它们连接成了一个神经网络。人工神经网络,结构也有些类似。许多个神经元(下图中的⚪)相连,构成了一个神经网络。人类大脑神经元细胞接收来自外部多个…
暂无图片
编程学习 ·

咸鱼软件应用—VMware下安装ubantu

咸鱼软件应用—VMware下安装ubantuubantu简介开源下载地址在VMware虚拟机安装ubantu系统 为了测试固件需要安装Linux系统,后面有测试说明。现在先把ubantu系统装上再说~ubantu简介 ubuntu基于linux的免费开源桌面PC操作系统,十分契合英特尔的超极本定位,支持x86、64位和ppc架…
暂无图片
编程学习 ·

Vue——09——v-for和key指令

遍历普通数组 <!DOCTYPE html> <html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><title>Document</title><scri…
暂无图片
编程学习 ·

硕彦博创李飞授-------计算机基础及C语言变量

一、计算机基础 计算机只能识别二进制; 1.存储单位 最小存储单位:bit(比特) ----- 存储 0和1 基本存储单位:byte(字节) ----- 1byte = 8bit 其他单位:理论上 1KB = 1024B 1MB = 1024KB 1GB= 1024MB 1TB = 1024 GB Ps: 工业上:1Gb = 1000Mb 2.数制位: 二进制:满2进1,…
暂无图片
编程学习 ·

Java设计模式-5.适配器设计模式

在使用监听器的时候,需要定义一个类事件监听器接口,通常接口中有多个方法,而程序中不一定都用到,但又必须重写很繁琐,定义监听器时只要继承适配器,然后重写需要的方法。 适配器原理:适配器就是一个类,实现了监听器接口,所有抽象方法都重写了,但是方法都是空的,只重写…
暂无图片
编程学习 ·

java学习笔记6

1,找出最大元素的最小下标值 double max = myList[0]; int indexofMax = 0; for (int i=0;i<myList.length;i++){if(myList[i] > max){max = myList[i];indexofMax = i;} }用一次循环就找到了最大值,每次循环都将得到的较大数,在下一次循环中与新加入的数比较,在循环结…
暂无图片
编程学习 ·

Spring Boot内嵌Tomcat临时目录问题

最近发现线上一个项目日志突然报错,最终找到解决方法记录一下原因参考 https://github.com/spring-projects/spring-boot/issues/5009tmpwatch – removes files which haven’t been accessed for a period of time如上所言,删除指定的目录中一段时间未访问的文件。一般对于…
暂无图片
编程学习 ·

Spring中MultipartHttpServletRequest实现文件上传

实现图片上传 用户必须能够上传图片,因此需要文件上传的功能。比较常见的文件上传组件有Commons FileUpload(http://jakarta.apache.org/commons/fileupload/a>)和COS FileUpload(http://www.servlets.com/cos),Spring已经完全集成了这两种组件,这里我们选择Commons …
暂无图片
编程学习 ·

贪心算法经典例题

贪心算法:每次都取最佳 牛吃草 链接:https://ac.nowcoder.com/acm/problem/24867 来源:牛客网 Each of Farmer John’s N (1 <= N <= 50,000) cows likes to graze in a certain part of the pasture, which can be thought of as a large one-dimeensional number li…
暂无图片
编程学习 ·

Unity获取Terrain的尺寸

UnityUnity获取Terrain的尺寸 Unity获取Terrain的尺寸 对于Unity的策略游戏,可能会根据场景的大小来进行移动摄像机的限制,如何来获取地形的大小呢? 可以从Terrain对象的terrainData属性中获取size,详见代码:GameObject terrainObj = GameObject.FindGameObjectWithTag(&qu…
暂无图片
编程学习 ·

力扣简单题 169. 多数元素(摩尔投票法)

题目: 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [3,2,3] 输出: 3示例2: 输入: [2,2,1,1,1,2,2] 输出: 2做法分析: 对于2,2,1,3,1,…
暂无图片
编程学习 ·

Spring Cloud动态配置实现原理与源码分析

实际项目开发中少不了各种配置,如连接数据库的配置、连接 Redis 集群的配置等,通常我们也会为一个项目部署到每个环境准备不同的配置文件,例如测试环境配置连接测试的数据库。基本上静态配置就已经满足日常需求,但是静态配置缺少灵活性,一经修改就需要重新构建部署应用,同…
暂无图片
编程学习 ·

1. M601 ADC 的使用

1 ADC 相关的数据结构和 API1.1 概论OpenCPU 支持两个模拟输入引脚可用于检测外部电压。请参照管脚定义和ADC 硬件特性。 可以检测的电压范围可分四挡,分别是 1V,2V,3V。本文介绍的数据结构和 API 可以参考 SDK 中 Zyf_adc.h 文件。1.2 用法直接调用 ZYF_AdcRead 接口即可读…
暂无图片
编程学习 ·

LeetCode 378. 有序矩阵中第K小的元素 C++

方法一 解题思路m行n列的矩阵每一行相当于一个排好序的数组,要求出第k大的数,需要对这m行一维数组进行最小堆的建立,选出第k大的元素。可以用STL中的优先队列实现,这里实现需要定义一个结构体,同时对结构体的小于号也要进行重载。结构体定义 struct Point{int val;int x;i…