当前位置: 首页 > article >正文

Day15:二叉树的后续遍历序列

请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。

示例 1:

输入: postorder = [4,9,6,5,8]
输出: false 
解释:从上图可以看出这不是一颗二叉搜索树

LCR 152. 验证二叉搜索树的后序遍历序列 - 力扣(LeetCode)

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        if(postorder == null || postorder.length == 0 || postorder.length == 1){
            return true;
        }

        int length = postorder.length - 1;
        int root = postorder[length];

        int index = 0;
        //遍历出左子树节点
        for(int i = 0; i < length; i++){
            if(postorder[i] > root){
                index = i;
                break;
            }
        }
        if (index == 0 && postorder[index] < root) {
            index = length; // 右子树为空
        }
        //从这开始都应该是比根大了
        for(int j = index; j <length; j++ ){
            if(postorder[j] < root)
                 return false;
        }

         // 处理左子树
        int[] left = new int[0]; // 默认左子树为空
        if (index > 0) {
            left = Arrays.copyOfRange(postorder, 0, index);
        } 
        // 处理右子树
        int[] right = new int[0]; // 默认右子树为空
        if (index < length) {
            right = Arrays.copyOfRange(postorder, index, length);
        } 
        return verifyTreeOrder(left)&&verifyTreeOrder(right);
    }
}

要注意函数调用的边界。Arrays.copyOfRange(postorder, 0, index) 是复制从索引 0 到 index - 1 的元素,而不是复制到 index。在这里栽坑了。然后就是右子树为空的情况,因为没有比他大的元素,所以index不会变,deepseek让我加一个判断,我觉得应该是我代码本身的纰漏。选择把index的更新放在判断体的外面就行了(基本功不好)

 

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        if(postorder == null || postorder.length == 0 || postorder.length == 1){
            return true;
        }

        int length = postorder.length - 1;
        int root = postorder[length];

        int index = 0;
        //遍历出左子树节点
        for(; index < length; index++){
            if(postorder[index] > root){
                break;
            }
        }

        for(int j = index; j <length; j++ ){
            if(postorder[j] < root)
                 return false;
        }

         // 处理左子树
        int[] left = new int[0]; // 默认左子树为空
        if (index > 0) {
            left = Arrays.copyOfRange(postorder, 0, index);
        } 
        // 处理右子树
        int[] right = new int[0]; // 默认右子树为空
        if (index < length) {
            right = Arrays.copyOfRange(postorder, index, length);
        } 
        return verifyTreeOrder(left)&&verifyTreeOrder(right);
    }
}


http://www.kler.cn/a/583890.html

相关文章:

  • C#中类‌的核心定义
  • 【存储中间件】Redis核心技术与实战(一):Redis入门与应用(常用数据结构:字符串String、哈希Hash、列表List)
  • LLM:了解大语言模型
  • OBS推WebRTC流,并添加毫秒级时间显示
  • K8S中的etcd数据库备份与恢复
  • 树莓百度百科更新!宜宾园区新业务板块全解析
  • 建筑兔零基础自学记录45|获取高德/百度POI-1
  • AI理论基础
  • 重生之我在学Vue--第12天 Vue 3 性能优化实战指南
  • SpaceSync智能排班:重构未来办公空间的神经中枢
  • 聚划算!三个模型对比预测!CNN-GRU、GRU、CNN三模型多变量时序光伏功率预测
  • 基于boss直聘的招聘数据可视化分析平台-Flask+html
  • PAT乙级(1022 D进制的A+B)C语言
  • ADC采样和存储数据之间的关系
  • 一键阐述“多线程、多进程、多任务”的场景需求
  • Deepseek Chatgpt Kimi 推荐的深度学习书单
  • OpenRewrite配方之import语句的顺序——org.openrewrite.java.OrderImports
  • Spring(一)
  • 工具(十二):Java导出MySQL数据库表结构信息到excel
  • 5G/6G通信技术