【LeetCode剑指offer33】二叉搜索树的后序遍历序列(找分界点)

简介: 单纯根据后序遍历序列,不阔能确定一棵二叉树,但是事先说明是二叉搜索树BST了,BST树的特点是中序遍历序列,是有序序列,而且根结点val大于左孩子val,小于右孩子val。

一、题目


image.png

二、思路

单纯根据后序遍历序列,不阔能确定一棵二叉树,但是事先说明是二叉搜索树BST了,BST树的特点是中序遍历序列,是有序序列,而且根结点val大于左孩子val,小于右孩子val。


而且题目给出后序遍历序列,最后一个节点是根结点,我们就能从头遍历数组,找到第一个比根结点大的节点位置(分界点),在此前面的部分,都是根结点的左子树部分;分界点后面部分理应是右子树部分,所以val也理应该大于根结点。所以基于这点,我们只要判断分界点后的结点值,是否有小于根结点的这种异常情况,则说明不是BST的后序序列。


三、代码

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return dfs(postorder, 0, postorder.size() - 1);
    }   
    bool dfs(vector<int>& postorder, int left, int right){
        //如果数组中只剩下一个元素或没有元素,则肯定满足
        if(left >= right){
            return true;
        }
        int temp = left;
        //找分界点
        while(postorder[temp] < postorder[right]){
            temp++;
        }
        int a = temp;
        //判断分界点后面的结点val,是否还有小于根结点val的
        while(temp < right){
            if(postorder[temp++] < postorder[right]){
                return false;
            }
        }
        return dfs(postorder, left, a - 1) 
               && dfs(postorder, a, right - 1);
    }
};
相关文章
|
3月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
109 1
|
5月前
|
存储 算法 数据可视化
【二叉树遍历入门:从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图(详细解析)(Go语言版)
本文详细解析了二叉树的三种经典遍历方式:中序遍历(94题)、层序遍历(102题)和右视图(199题)。通过递归与迭代实现中序遍历,深入理解深度优先搜索(DFS);借助队列完成层序遍历和右视图,掌握广度优先搜索(BFS)。文章对比DFS与BFS的思维方式,总结不同遍历的应用场景,为后续构造树结构奠定基础。
236 10
|
11月前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
58 1
|
11月前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
70 1
|
11月前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
95 0
|
11月前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
56 0
|
11月前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
81 0
|
12月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
170 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
130 6
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
282 2

热门文章

最新文章