[剑指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;
    }
};

热门文章

暂无图片
编程学习 ·

超星尔雅《中庸》精读

超星学习通app《中庸》精读 答案 孟琢“四书”的形成(一)1【单选题】著作( )是一部论述了人生修养境界的道德哲学专著。 答案:《中庸》A、《周易》B、《史记》C、《诗经》D、《中庸》2【单选题】中国古代思想家( )是儒家学派的创始人,被后世尊称为万世师表。 答案:孔子A、孔…
暂无图片
编程学习 ·

ARM特殊寄存器详解

ARM特殊寄存器详解 arm特殊寄存器arm汇编访问特殊寄存器 可以使用MRS和MSR特殊寄存器访问指令来访问特殊寄存器。MRS:读特殊寄存器 MSR:写特殊寄存器注意:MSP、PSP也要使用特殊寄存器访问指令来操作。 PSR特殊寄存器 APSR、EPSR、IPSR寄存器xPSR特殊寄存器arm各种架构PSR比较…
暂无图片
编程学习 ·

自定义控件三部曲之动画篇(四)——ValueAnimator基本使用

一、概述前面,我写过几篇有关Animation的文章,讲解了传统的alpha、scale、translate、rotate的用法及代码生成方法。其实这三篇文章讲的所有动画效果叫做Tween Animation(补间动画)在Android动画中,总共有两种类型的动画View Animation(视图动画)和Property Animator(属性…
暂无图片
编程学习 ·

Centos7x破解密码

办法一 1、开机启动部分1)开机e 选择第一行 e 2)找到Linux16所在行 ***.UTF8后面添加 rd.break console=tty0 3)ctrl + X2、启动到内核部分1)挂载/sysroot目录 #mount -o remount,rw /sysroot 2)切换到/sysroot目录 #chroot /sysroot 3)修改root密码 #echo passwo…
暂无图片
编程学习 ·

postman引入文件实现参数化及中文乱码问题解决

1、首先,在postman中输入地址和参数,保证接口请求成功。可以在tests中添加断言2、将需要参数化的参数用变量表示,并将变量添加进全局变量中3、将需要参数化的参数写成CSV,TXT,JSON格式的文档。这里用的是csv格式的文件,其中name是变量名如果用txt格式的文件,多参数之间要用…
暂无图片
中恒嘉业 ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
郑州普通话 ·

[Redux/Mobx] Redux和vuex有什么区别?

[Redux/Mobx] Redux和vuex有什么区别&#xff1f; 1&#xff1a;vuex的异步数据不需要使用到中件间&#xff0c;redux需要 2&#xff1a;vuex可以直接commit&#xff0c;action不是必须的&#xff0c;redux是必须的 个人简介 我是歌谣&#xff0c;欢迎和大家一起交流前后端知…
暂无图片
郑州普通话 ·

flex布局常见的一些案例

风华正茂的年纪遇到你&#xff0c;是我最大的幸运&#xff0c;谢谢你&#xff0c;靠近我&#xff0c;了解我&#xff0c;治愈我&#xff0c;陪着我&#xff0c;谢谢你来爱我。 flex是啥&#xff1a;是一种弹性布局方式。&#xff08;注意这个弹&#xff09; flex属性值大全&…
暂无图片
代理记账 ·

[Redux/Mobx] Redux和vuex有什么区别?

[Redux/Mobx] Redux和vuex有什么区别&#xff1f; 1&#xff1a;vuex的异步数据不需要使用到中件间&#xff0c;redux需要 2&#xff1a;vuex可以直接commit&#xff0c;action不是必须的&#xff0c;redux是必须的 个人简介 我是歌谣&#xff0c;欢迎和大家一起交流前后端知…
暂无图片
代理记账 ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
cgfy ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
coreui ·

[Redux/Mobx] Redux和vuex有什么区别?

[Redux/Mobx] Redux和vuex有什么区别&#xff1f; 1&#xff1a;vuex的异步数据不需要使用到中件间&#xff0c;redux需要 2&#xff1a;vuex可以直接commit&#xff0c;action不是必须的&#xff0c;redux是必须的 个人简介 我是歌谣&#xff0c;欢迎和大家一起交流前后端知…
暂无图片
未来博客 ·

[Redux/Mobx] Redux和vuex有什么区别?

[Redux/Mobx] Redux和vuex有什么区别&#xff1f; 1&#xff1a;vuex的异步数据不需要使用到中件间&#xff0c;redux需要 2&#xff1a;vuex可以直接commit&#xff0c;action不是必须的&#xff0c;redux是必须的 个人简介 我是歌谣&#xff0c;欢迎和大家一起交流前后端知…
暂无图片
建站日记 ·

[Redux/Mobx] Redux和vuex有什么区别?

[Redux/Mobx] Redux和vuex有什么区别&#xff1f; 1&#xff1a;vuex的异步数据不需要使用到中件间&#xff0c;redux需要 2&#xff1a;vuex可以直接commit&#xff0c;action不是必须的&#xff0c;redux是必须的 个人简介 我是歌谣&#xff0c;欢迎和大家一起交流前后端知…
暂无图片
mfbz ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
mfbz ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
珊珊日记 ·

学习笔记六——循环神经网络

一、RNN 前馈神经网络&#xff1a;信息往一个方向流动。包括MLP和CNN 循环神经网络&#xff1a;信息循环流动&#xff0c;网络隐含层输出又作为自身输入&#xff0c;包括RNN、LSTM、GAN等。 RNN模型结构如下图所示&#xff1a; 展开之后相当于堆叠多个共享隐含层参数的前馈…
暂无图片
珊珊日记 ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…