代码随想录算法训练营第23天|669.修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树、总结篇

本文主要是介绍代码随想录算法训练营第23天|669.修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树、总结篇,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 一、力扣669.修剪二叉搜索树
    • 1.1 题目
    • 1.2 思路
    • 1.3 代码
  • 二、力扣108.将有序数组转换为二叉搜索树
    • 2.1 题目
    • 2.2 思路
    • 2.3 代码
    • 2.4 总结
  • 三、力扣538.把二叉搜索树转换为累加树
    • 3.1 题目
    • 3.2 思路
    • 3.3 代码
    • 3.4 总结

一、力扣669.修剪二叉搜索树

1.1 题目

在这里插入图片描述

1.2 思路

本题递归代码分三个模块来写:
(1)递归终止条件:null节点
(2)该节点为要删除节点的处理逻辑:继续向左或者向右递归,将有效的节点返回给上层节点
(3)该节点为不需要删除节点的处理逻辑:继续向左和又递归,将有效的节点返回给本节点作为左右孩子

1.3 代码

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {//判断特殊情况if(root == null){return null;}return traversal(root,low,high);}//递归public TreeNode traversal(TreeNode root,int low,int high){//递归终止条件if(root == null){return null;}//如果当前节点是需要被删除的节点if(root.val < low){return traversal(root.right,low,high);}if(root.val > high){return traversal(root.left,low,high);}//如果该节点符合条件,不需要被删除root.left = traversal(root.left,low,high);root.right = traversal(root.right,low,high);return root;}
}

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

2.1 题目

在这里插入图片描述

2.2 思路

注意是平衡二叉搜索树;
选取二叉树的中间节点(数组的中间数),根据数组的左右区间来构造二叉树的左右子树。

2.3 代码

lass Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length == 0){return null;}return traversal(nums,0,nums.length-1);}//递归,划分区间构造左右子树(坚持区间左闭右闭原则)public TreeNode traversal(int[] nums,int left,int right){//递归终止条件if(left > right){return null;}int mid = left +((right-left)>>1);//注意使用移位运算符要加括号TreeNode root = new TreeNode(nums[mid]);root.left = traversal(nums,left,mid-1);root.right = traversal(nums,mid+1,right);return root;}
}

2.4 总结

构造二叉树:有序数组选取中间节点,然后递归划分左右区间构造左右子树。
注意使用移位运算符要加括号。

三、力扣538.把二叉搜索树转换为累加树

3.1 题目

在这里插入图片描述

3.2 思路

我的思路:先将二叉树中序遍历一遍,将值记录再数组中;
第二次中序遍历时直接累加赋值(设置一个起始索引,置为0,每遍历一个节点就起始索引加一,直到遍历结束)
代码随想录:右中左

3.3 代码

我的思路:(跑出来是错的)

class Solution {public List<Integer> res = new ArrayList<>();public int quitIndex = -1; public TreeNode convertBST(TreeNode root) {if(root == null){return null;}//第一次中序遍历,从小到大拿到所有节点的值traversal(root);//第二次遍历,为节点重新赋值int sum = 0;for(int i =0;i<res.size();i++){sum += res.get(i);}traversal2(root,sum);return root;}public void traversal(TreeNode root){if(root == null){return;}//左中右traversal(root.left);res.add(root.val);traversal(root.right);}public void traversal2(TreeNode root,int sum){if(root == null){return;}//左中右traversal2(root.left,sum);if(quitIndex != -1){sum -= res.get(quitIndex);root.val = sum;quitIndex++;}else{root.val = sum;quitIndex++;}traversal2(root.right,sum);}
}

右中左(相当于从大到小遍历):

class Solution {public int beforeSum = 0;public TreeNode convertBST(TreeNode root) {//右中左递归遍历(按值从大到小)if(root == null){return null;}traversal(root);return root;}public void traversal(TreeNode root){if(root == null){return;}traversal(root.right);//中:更新本节点的值beforeSum += root.val;root.val = beforeSum;traversal(root.left);}
}

3.4 总结

还是要利用好二叉搜索树的有序特性!

二叉树总结参考代码随想录:https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html#%E6%9C%80%E5%90%8E%E6%80%BB%E7%BB%93
在这里插入图片描述

这篇关于代码随想录算法训练营第23天|669.修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树、总结篇的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/796153

相关文章

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C#实现将Excel表格转换为图片(JPG/ PNG)

《C#实现将Excel表格转换为图片(JPG/PNG)》Excel表格可能会因为不同设备或字体缺失等问题,导致格式错乱或数据显示异常,转换为图片后,能确保数据的排版等保持一致,下面我们看看如何使用C... 目录通过C# 转换Excel工作表到图片通过C# 转换指定单元格区域到图片知识扩展C# 将 Excel

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析