DAY21|二叉树Part08|LeetCode: 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

news/2024/12/14 12:16:35/

目录

LeetCode: 669. 修剪二叉搜索树

基本思路

C++代码

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

基本思路

C++代码

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

基本思路

C++代码


LeetCode: 669. 修剪二叉搜索树

力扣代码链接

文字讲解:LeetCode: 669. 修剪二叉搜索树

视频讲解:你修剪的方式不对,我来给你纠正一下!

基本思路

        这个题目比较简单,但是一定要注意遇到节点在目标区间以外,不能直接返回null,而是应该继续向下判定,因为对于一个搜索二叉树来讲,在遍历整个二叉树的节点的过程中,如果某个节点的值小于区间的最小值,对于该节点的左子树中的所有节点一定都小于目标区间的最小值,但是右子树中却可能存在符合目标区间的值,因此还需要进一步进行判定。

  • 确定递归函数的参数以及返回值

        参数:需要传入当前遍历的节点,还需要传入目标取件的边界值low和high。

        返回值:返回需要删除的节点。

TreeNode* trimBST(TreeNode* root, int low, int high)
  • 确定终止条件

        修剪的操作并不是在终止条件上进行的,所以就是遇到空节点返回就可以了。

if (root == nullptr ) return nullptr;
  • 确定单层递归的逻辑

        如果root(当前节点)的元素小于low的数值,那么应该递归右子树,并返回右子树符合条件的头结点。

if (root->val < low) {TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点return right;
}

        如果root(当前节点)的元素大于high的,那么应该递归左子树,并返回左子树符合条件的头结点。

if (root->val > high) {TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点return left;
}

        接下来要将下一层处理完左子树的结果赋给root->left,处理完右子树的结果赋给root->right。

root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;

C++代码

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); // 寻找符合区间[low, high]的节点return right;}if (root->val > high) {TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点return left;}root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子return root;}
};

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

力扣代码链接

文字讲解:LeetCode: 108.将有序数组转换为二叉搜索树

视频讲解:构造平衡二叉搜索树!

基本思路

        构建平衡二叉树是为因为给定任意一个有序数组,都可以直接构建一颗线性结构的二叉树。而构建二叉树我们首先就应该想到根据数组构建二叉树,本质就是寻找分割点,分割点作为当前节点,然后递归左区间和右区间分割点就是数组中间位置的节点。

  • 确定递归函数返回值及其参数

        参数:需要传入一个有序数组,并且需要传入数组的左右下标(根据数组的左右下标来构建二叉树)

        返回值:返回构建二叉树的根节点。

// 左闭右闭区间[left, right]
TreeNode* traversal(vector<int>& nums, int left, int right)

        这里注意,我这里定义的是左闭右闭区间,在不断分割的过程中,也会坚持左闭右闭的区间,这又涉及到我们讲过的循环不变量原则

  • 确定递归终止条件

        这里定义的是左闭右闭的区间,所以当区间left>right当时候,就是空结点了。

if (left > right) return nullptr;
  • 确定单层递归的逻辑

        根据数组区间的左右下标来构建二叉树,其中二叉树的根节点为mid = left+(right-left)/2,此时中间节点为:

TreeNode* root = new TreeNode(nums[mid]);

        接着划分区间,root的左孩子接住下一层左区间的构造节点,右孩子接住下一层右区间构造的节点,最后返回root节点。

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;

C++代码

class Solution {
private: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;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {TreeNode* root = traversal(nums, 0, nums.size() - 1);return root;}
};

        注意:在调用traversal的时候传入的left和right为什么是0和nums.size() - 1,因为定义的区间为左闭右闭

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

力扣代码链接

文字讲解:LeetCode: 538.把二叉搜索树转换为累加树

视频讲解:普大喜奔!二叉树章节已全部更完啦!

基本思路

        其实这就是一棵树,大家可能看起来有点别扭,换一个角度来看,这就是一个有序数组[2, 5, 13],求从后到前的累加数组,也就是[20, 18, 13],是不是感觉这就简单了。

        为什么变成数组就是感觉简单了呢?

        因为数组大家都知道怎么遍历啊,从后向前,挨个累加就完事了,这换成了二叉搜索树,看起来就别扭了一些是不是。那么知道如何遍历这个二叉树,也就迎刃而解了,从树中可以看出累加的顺序是右中左,所以我们需要反中序遍历这个二叉树,然后顺序累加就可以了。

  • 递归函数参数以及返回值

        首先需要定义一个全局变量pre,用来记录前一个节点的值。

        参数:传入当前节点

        返回值:只需要对遍历的节点的值进行操作,不需要什么返回值。

int pre = 0; // 记录前一个节点的数值
void traversal(TreeNode* cur)
  • 确定终止条件

        遇空节点就终止。

if (cur == NULL) return;
  • 确定单层递归的逻辑

        注意要右中左来遍历二叉树, 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。

traversal(cur->right);  // 右
cur->val += pre;        // 中
pre = cur->val;
traversal(cur->left);   // 左

C++代码

class Solution {
private:int pre = 0; // 记录前一个节点的数值void traversal(TreeNode* cur) { // 右中左遍历if (cur == NULL) return;traversal(cur->right);cur->val += pre;pre = cur->val;traversal(cur->left);}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};

http://www.ppmy.cn/news/1545095.html

相关文章

常见几种GB 9706.1-2020医疗器械试验工装,您有所了解吗?

医疗器械试验工装是指用于医疗器械试验的工具或器具。它们可以用于测试医疗器械的性能、安全性和有效性&#xff0c;以确保医疗器械符合相关的标准和法规要求。Delta德尔塔仪器医疗器械试验工装&#xff0c;符合GB 9706.1-2020标准要求。 常见的医疗器械试验工装包括&#xff1…

全文检索ElasticSearch到底是什么?

学习ElasticSearch之前&#xff0c;我们先来了解一下搜索 1 搜索是什么 ① 概念&#xff1a;用户输入想要的关键词&#xff0c;返回含有该关键词的所有信息。 ② 场景&#xff1a; ​ 1互联网搜索&#xff1a;谷歌、百度、各种新闻首页&#xff1b; ​ 2 站内搜索&#xff…

502 Bad Gateway 错误详解:从表现推测原因,逐步排查直至解决

502 Bad Gateway 错误通常意味着服务器之间的通信失败&#xff0c;但导致的具体原因往往因场景而异。 场景一&#xff1a;高峰期频繁出现 502 错误 1.1 现象 在流量高峰期间&#xff08;如促销活动、直播发布等&#xff09;&#xff0c;页面访问变慢甚至出现 502 错误&#…

腾讯cos对象存储,下行流量费贵,是否可以加入服务器减少费用,架构如何设计

腾讯云COS&#xff08;Cloud Object Storage&#xff09;对象存储服务提供了一种高效、安全、低成本的方式存储大量数据。然而&#xff0c;当涉及到外网下行流量时&#xff0c;确实会产生一定的费用&#xff0c;这可能会增加整体的成本。为了减少这些费用&#xff0c;可以通过以…

UE4_Niagara基础实例—15、粒子发射器之间的通信

效果&#xff1a; 分析&#xff1a; 要想让第二个发射器产生的粒子向第一个发射器产生的粒子靠齐&#xff0c;我们就需要用到点吸引力或者点排斥力&#xff0c;同时得到第一个发射器粒子的位置就可以了&#xff0c;要想得到第一个发射器粒子位置&#xff0c;那么我们就得需要粒…

【大数据学习 | kafka高级部分】文件清除原理

2. 两种文件清除策略 kafka数据并不是为了做大量存储使用的&#xff0c;主要的功能是在流式计算中进行数据的流转&#xff0c;所以kafka中的数据并不做长期存储&#xff0c;默认存储时间为7天 那么问题来了&#xff0c;kafka中的数据是如何进行删除的呢&#xff1f; 在Kafka…

C++之旅——入门

Hello&#xff0c;各位小伙伴们&#xff0c;前几期我们学习了C语言和数据结构&#xff0c;有了一定的基础之后我们来挑战新的语言——C。 目录 一、初识C 1>C发展历史 2>C版本更新 3>C的热度 4>C的学习难度 5>C学习相关书籍 二、第一个C代码 三、C基础 …

[晕事]今天做了件晕事50 dev_ioctl 里没有SIOCADDTUNNEL?

今天又晕了一下&#xff0c;在看添加GRE隧道的代码&#xff0c;发现这个dev_ioctl里没有关于这个SIOCADDTUNNEL处理&#xff1f; 后来发现不是没有&#xff0c;而是被下面的代码覆盖了&#xff0c;虽然没有明写case语句&#xff0c;但是if判断里已经包含了&#xff0c;使用了大…