代码随想录day20--二叉树的应用8

news/2024/2/21 3:27:38

LeetCode669.修剪二叉搜索树

题目描述:

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

示例 1:

输入:root = [1,0,2], low = 1, high = 2
输出:[1,null,2]

示例 2:

输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出:[3,2,null,1]

解题思路:

·思路其实和上一篇中的删除节点是类似的,只是需要将二叉树全部遍历

·并且需要考虑题目给定的区间,删除掉区间外的元素后,再将元素与其父节点连接

·需要利用好二叉搜索树的特性,若一个节点的值小于区间内的最小值,则其节点的左树上全部不符合条件,可以直接删除,同理,若一个节点的值大于区间内的最大值,则其节点的右树上全部不符合条件,亦可以直接删除。

代码如下:

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == nullptr) return nullptr;if(root->val < low){//删除左树中不符合的元素TreeNode* right = trimBST(root->right,low,high);return right;}if(root->val > high){//删除右树中不符合的元素TreeNode* left = trimBST(root->left,low,high);return left;}root->left = trimBST(root->left,low,high);//遍历符合条件的左孩子root->right = trimBST(root->right,low,high);//遍历符合条件的右孩子return root;}
};

易错点:

·依旧是二叉树中的重构,如果看代码看不懂,可以尝试画图进行尝试

总结:这道题其实不难,但是理解起来可能会有些费劲,需要对递归的理解有比较深刻的认识

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

题目描述:

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1:

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

示例 2:

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

解题思路:
·找到数组的中元素值,再进行二叉搜索树的排序,即可解答

·需要注意的是,我们需要构建一个平衡二叉树,否则题目就毫无意义了

·不需要先确定根节点,再从头进行遍历构建二叉树,只需要确定了中间节点,再向左和向右遍历,即可很快的求解出

代码如下:

class Solution {
public:TreeNode* traversal(vector<int>& nums,int left,int right){if(left>right) return nullptr;int mid = left + ((right-left)/2);TreeNode* root = new TreeNode(nums[mid]);root->left = traversal(nums,left,mid-1);root->right = traversal(nums,mid+1,right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {TreeNode* root = traversal(nums,0,nums.size()-1);return root;}
};

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

题目描述:

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下,二叉搜索树满足下列约束条件:

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

示例 1:

输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2:

输入:root = [0,null,1]
输出:[1,null,1]

示例 3:

输入:root = [1,0,2]
输出:[3,3,2]

示例 4:

输入:root = [3,2,4,1]
输出:[7,9,4,10]

解题思路:
·需要明白题目中所说的累加树的定义,是从右子树中的节点开始向上累加,也就是使用右中左的方式进行遍历累加。

·得出右中左的遍历方式后,我们即可得知,与中序遍历相关,也就是使用反中序遍历进行解题

代码如下:

class Solution {
public:int pre = 0;void traversal(TreeNode* cur){if(cur == NULL) return ;traversal(cur->right);cur->val += pre;pre = cur->val;traversal(cur->left);}TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};

总结:经过这么久的二叉树基本应用的练习,今天的题目的难度以及逻辑理解起来并不会很困难,二叉树的基本应用环节到此也就告一段落了。


https://www.xjx100.cn/news/3271245.html

相关文章

【Java程序设计】【C00257】基于Springboot的校园二手书交易平台(有论文)

基于Springboot的校园二手书交易平台&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的乐校园二手书交易管理系统 本系统分为系统功能模块、管理员功能模块、卖家用户功能模块以及用户功能模块。 系统功能模块&…

应急响应实战笔记02日志分析篇(2)

第2篇:Linux日志分析 0x00 前言 Linux系统拥有非常灵活和强大的日志功能&#xff0c;可以保存几乎所有的操作记录&#xff0c;并可以从中检索出我们需要的信息。 本文简介一下Linux系统日志及日志分析技巧。 0x01 日志简介 日志默认存放位置&#xff1a;/var/log/ 查看日志…

算法学习——LeetCode力扣二叉树篇5

算法学习——LeetCode力扣二叉树篇5 513. 找树左下角的值 513. 找树左下角的值 - 力扣&#xff08;LeetCode&#xff09; 描述 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 示例 1: 输入: r…

C# CAD交互界面-自定义面板集-查找定位(六)

运行环境 vs2022 c# cad2016 调试成功 一、代码说明 1. 类成员变量声明&#xff1a; List<ObjectId> objectIds new List<ObjectId>(); // 用于存储AutoCAD实体对象的ObjectId列表 private static Autodesk.AutoCAD.Windows.PaletteSet _ps2; // 自定义浮动面板…

2024年教师资格证认定报名完整流程

&#x1f49a;网上报名流程概览 一、进入教资认定网报入口&#xff1b; 二、进行实名核验&#xff1b; 三、申请网报时间查询&#xff1b; 四、个人信息维护&#xff1b; 五、认定申请报名&#xff1b; &#x1f49a;认定所需材料 1、 身份证&#xff1b; 2 、户口本/居住证…

nba2k24 韩旭面补

nba2k23-24 韩旭面补 nba2k23-nba2k24通用 韩旭面补 下载地址&#xff1a; https://www.changyouzuhao.cn/9605.html

使用Docker快速部署MySQL

部署MySQL 使用Docker安装&#xff0c;仅仅需要一步即可&#xff0c;在命令行输入下面的命令 docker run -d \--name mysql \-p 3306:3306 \-e TZAsia/Shanghai \-e MYSQL_ROOT_PASSWORD123456 \mysql MySQL安装完毕&#xff01;通过任意客户端工具即可连接到MySQL. 当我们执…

车载诊断协议DoIP系列 —— 协议中的简易网络拓扑概述

车载诊断协议DoIP系列 —— 协议中的简易网络拓扑概述 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自己。江湖一碗…