专栏首页CtrlCV博客【剑指Offer】二叉搜索树的后序遍历序列

【剑指Offer】二叉搜索树的后序遍历序列

题目

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

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

 5
/ \

2 6 / 1 3 示例 1:

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

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

提示:

数组长度 <= 1000

题解

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i])
            	root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • QQ二维码登录API源码

    小新哟
  • QQ二维码登录API源码

    小新哟
  • 【剑指Offer】二叉树中和为某一值的路径

    输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

    小新哟
  • 这道题有“圈套" 基础不好很容易上套!

    上面这行代码,~的优先级最高,首先肯定是对a进行按位取反,然后是+的优先级较高,所以执行4+1 =5,最后执行右移操作。

    7089bAt@PowerLi
  • WordPress 站点地址被恶意篡改的防护方案讨论

    WordPress 站点的安全性非常重要,稍有不慎就有可能受到恶意攻击。一种常见的手段是通过篡改站点的地址,于是用户访问网站时将会被重新定向到恶意网站。

    凝神长老
  • 剑指offer - 顺时针打印矩阵 - JavaScript

    题目描述:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下 4 X 4 矩阵: 1 2 3 4 5 6 7 8 9 10 11 ...

    心谭博客
  • 古典:那声轻微的破碎声

    环游世界的豪华游轮正在航行在北大西洋上。晚上八点,豪华的舞会正在进行,人们盛装在船上穿梭。突然,船底部甲板传来震动,伴随着船底部传来的轻微破裂声。有些乐师听见,...

    用户1756920
  • Leetcode: Maximum Subarray

    题目: Find the contiguous subarray within an array (containing at least one num...

    卡尔曼和玻尔兹曼谁曼
  • MMD_3b_StreamAlgorithms

    Stream概述 DBMS的区别 Stream模型 Query种类 应用 Sliding Windows 简介 例子 Bloom Filter motivati...

    用户1147754
  • 黑客入侵大量“肉鸡”后用来干嘛?

    “肉鸡”也称傀儡机,是指可以被黑客远程控制的机器。比如用"灰鸽子"等诱导客户点击或者电脑被黑客攻破或用户电脑有漏洞被种植了木马,黑客可以随意操纵它并利用它做任何...

    网e渗透安全部

扫码关注云+社区

领取腾讯云代金券