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

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

系列文章目录


目录

  • 系列文章目录
  • 669. 修剪二叉搜索树
    • ①递归法
    • ②迭代法(不好想出,掌握递归即可)
  • 108.将有序数组转换为二叉搜索树
    • 递归法
      • [左闭右开)
      • [左闭右闭]
  • 538.把二叉搜索树转换为累加树
    • ①递归法-反中序遍历(右中左)+双指针
    • ②迭代法-反中序遍历(右中左)+双指针
      • 统一迭代法
      • 普通迭代法


669. 修剪二叉搜索树

①递归法

:不能在遇到 root.val < low || root.val > high 的时候直接return null,因为下图所示:在这里插入图片描述
[1, 3]区间在二叉搜索树的中可不是单纯的节点3和左孩子节点0就决定的,还要考虑节点0的右子树。节点0并不符合区间要求,那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了(就是把节点0从二叉树中移除),如下图所示:
在这里插入图片描述

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {//确定终止条件if (root == null) return null;//确定单层递归的逻辑//中//如果root(当前节点)的元素小于low的数值,那么应该递归右子树,并返回右子树符合条件的头结点。if (root.val < low) {return trimBST(root.right, low, high);}//如果root(当前节点)的元素大于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;}
}

②迭代法(不好想出,掌握递归即可)

  1. 因为二叉搜索树的有序性,不需要使用栈模拟递归的过程。
  2. 在剪枝的时候,可以分为三步:
    • root移动到[L, R] 范围内,注意是左闭右闭区间;
    • 剪枝左子树;
    • 剪枝右子树;
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null) return null;//中 确定最后要返回的根节点while (root != null && (root.val < low || root.val > high)) {if (root.val < low) {root = root.right;} else {root = root.left;}}//在根节点一定在区间内的前提下,剪枝//左、对左子树剪枝,左子树的所有节点都小于high,只需要判断是否小于lowTreeNode curr = root;while (curr != null) {// 如果左节点的值小于low,证明左节点以及左节点的左子树都小于low,要剪掉,继续判断左节点的右子树即可while (curr.left != null && curr.left.val < low) {curr.left = curr.left.right;}// 现在的左节点大于等于low,则继续往左遍历curr = curr.left;}//右 对右子树剪枝,右子树的所有节点都大于low,只需要判断节点是否大于highcurr = root;// 如果右节点的值大于high,证明右节点以及右节点的的右子树都大于high,要剪掉,继续判断右节点的左子树即可while (curr != null) {while (curr.right != null && curr.right.val > high) {curr.right = curr.right.left;}// 现在的右节点小于等于high,则继续往右遍历curr = curr.right;}return root;}
}

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

本质就是寻找分割点,分割点作为当前节点,然后递归左区间和右区间。分割点就是数组中间位置的节点。如果数组长度为偶数,中间节点有两个,取哪一个都可以,只不过构成了不同的平衡二叉搜索树。

递归法

1.在构造二叉树的时候尽量不要重新定义左右区间数组,而是用下标来操作原数组。
2.取数组中间元素的位置,不难写出int mid = (left + right) / 2;,这么写其实有一个问题,就是数值越界,例如leftright都是最大int,这么操作就越界了,尤其需要注意!所以可以这么写:int mid = left + ((right - left) / 2);

[左闭右开)

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return makeBST(nums, 0, nums.length);}//左闭右开public TreeNode makeBST(int[] nums, int begin, int end) {//终止条件if (begin >= end) return null;//单层循环逻辑// 构建平衡二叉树的关键是选中间/靠近的节点作为根节点int index = begin + (end - begin) / 2;//中节点索引int rootVal = nums[index];TreeNode root = new TreeNode(rootVal);//构造根节点// 构建左右子树root.left = makeBST(nums, begin, index);root.right = makeBST(nums, index + 1, end);return root;}
}

[左闭右闭]

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return makeBST(nums, 0, nums.length - 1);}public TreeNode makeBST(int[] nums, int begin, int end) {//终止条件if (begin > end) return null;//单层循环逻辑int index = begin + (end - begin) / 2;int rootVal = nums[index];TreeNode root = new TreeNode(rootVal);//创建根节点root.left = makeBST(nums, begin, index - 1);root.right = makeBST(nums, index + 1, end);return root;}
}

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

这是一棵树,换一个角度来看,这就是一个有序数组[2, 5, 13],求从后到前的累加数组,也就是[20, 18, 13]。从树中可以看出累加的顺序是右中左,所以我们需要反中序遍历这个二叉树,然后顺序累加就可以了。本题依然需要一个pre指针记录当前遍历节点cur的前一个节点,这样才方便做累加。

①递归法-反中序遍历(右中左)+双指针

class Solution {TreeNode pre = null;int value = 0;public TreeNode convertBST(TreeNode root) {if (root == null) return null;root.right = convertBST(root.right);//右if (pre != null) {//中root.val += pre.val;}pre = root;root.left = convertBST(root.left);//左return root;}
}

②迭代法-反中序遍历(右中左)+双指针

统一迭代法

class Solution {public TreeNode convertBST(TreeNode root) {if (root == null) return null;Stack<TreeNode> st = new Stack<TreeNode>();st.push(root);TreeNode pre = null;while (!st.isEmpty()) {TreeNode node = st.peek();if (node != null) {st.pop();if (node.left != null) st.push(node.left);//左st.push(node);//中st.push(null);if (node.right != null) st.push(node.right);//右} else {//中节点处理逻辑st.pop();node = st.pop();if (pre != null) {node.val += pre.val;}pre = node;}}return root;}
}

普通迭代法

class Solution {public TreeNode convertBST(TreeNode root) {if (root == null) return null;Stack<TreeNode> st = new Stack<TreeNode>();TreeNode cur = root;TreeNode pre = null;while (cur != null || !st.isEmpty()) {if (cur != null) {st.push(cur);cur = cur.right;//右} else {cur = st.pop();//中if (pre != null) {cur.val += pre.val;}pre = cur;cur = cur.left;}}return root;}
}

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



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

相关文章

利用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)模拟实现队列(双链表实现)循环队列(循环数组

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. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的