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

Day23 二叉树09

 669. 修剪二叉搜索树 

题目链接:669. 修剪二叉搜索树 - 力扣(LeetCode)

思路:节点值不在区间式,返回的不是子节点,而是递归调度,而且根据二叉搜索树特征,该节点小于key则所有左子树都小于key,右子树同理。

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return null;
        if(root.val < low){
            return trimBST(root.right,low,high);
        }
        if(root.val > high){
            return trimBST(root.left,low,high);
        }

        root.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);

        return root;
    }
}

 108.将有序数组转换为二叉搜索树  

题目链接:108. 将有序数组转换为二叉搜索树 - 力扣(LeetCode)

思路:从中间节点开始

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST1(nums,0,nums.length);
    }

    public TreeNode sortedArrayToBST1(int[] nums, int left, int right){
        if(left>=right) return null;
        if(right - left == 1) return new TreeNode(nums[left]);
        int mid = left +(right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST1(nums,left,mid);
        root.right = sortedArrayToBST1(nums,mid+1,right);
        return root;
    }
}

 538.把二叉搜索树转换为累加树  

题目链接:538. 把二叉搜索树转换为累加树 - 力扣(LeetCode)

思路:双指针法,需要额外调度函数

class Solution {
    int pre;
    public TreeNode convertBST(TreeNode root) {
        pre = 0;
        convertBST1(root);
        return root;
    }

    public void convertBST1(TreeNode root){
        if(root == null) return;
        convertBST1(root.right);
        pre = pre + root.val;
        root.val = pre;
        convertBST1(root.left);
        return;
    }
}


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

相关文章:

  • 【JS】简单CSS简单JS写的上传进度条
  • 【Notepad++】---设置背景为护眼色(豆沙绿)最新最详细
  • 代码随想录第40天
  • 入门级捡垃圾工作站记录
  • 【分子材料发现】——GAP:催化过程中吸附构型的多模态语言和图学习(数据集处理详解)(二)
  • 数据库之连接池Druid
  • 晶圆制造过程中常用载具的类型
  • AI推介-多模态视觉语言模型VLMs论文速览(arXiv方向):2024.03.10-2024.03.15
  • QT自定义带参数信号与槽函数
  • PHP+MySQL开发组合:多端多商户DIY商城源码系统 带完整的搭建教程以及安装代码包
  • im-system学习
  • 嵌入式学习-ARM-Day4
  • 【FPGA】摄像头模块OV5640
  • Linux系统及操作 (05)
  • 【ESP32接入国产大模型之MiniMax】
  • Python入门(小白友好)
  • Springboot和Spring Cloud版本对应
  • ClickHouse--13--springboot+mybatis配置clickhouse
  • 红与黑(c++题解)
  • 【复现】【免费】基于多时间尺度滚动优化的多能源微网双层调度模型
  • springboot校服订购系统
  • 阿里云发布 AI 编程助手 “通义灵码”——VSCode更强了 !!
  • 考研失败, 学点Java打小工_Day3_卫语句_循环
  • 阿里云2核4G4M轻量应用服务器价格165元一年
  • [QJS xmake] 非常简单地在Windows下编译QuickJS!
  • MySQL数据自动同步到Es