Leetcode算法训练日记 | day23

一、修剪二叉搜索树

1.题目

Leetcode：第 669 题

给你二叉搜索树的根节点 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]

2.解题思路

利用二叉搜索树的性质来修剪树：任何节点的左子树中的所有节点的值都小于该节点的值，
任何节点的右子树中的所有节点的值都大于该节点的值。首先检查当前节点的值是否在 [low, high] 范围内。如果不在，根据当前节点的值与 low 和 high 的比较结果，递归地修剪掉不需要的子树。然后，递归地修剪当前节点的左右子树。最终，返回当前节点，因为它的值在保留范围内。

3.实现代码

#include <iostream>
#include <vector>
using namespace std;

// 定义一个结构体TreeNode，用于表示二叉树的节点。
struct TreeNode {
    int val; // 存储节点的值。
    TreeNode* left; // 指向该节点左子树的指针。
    TreeNode* right; // 指向该节点右子树的指针。
    // TreeNode的构造函数，用于创建一个TreeNode实例。
    // 参数x是节点的值，left和right默认为NULL，表示没有左右子节点。
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 一、修剪二叉搜索树（递归法）
class Solution {
public:
    // 定义一个名为trimBST的公共成员函数，接受三个参数：二叉搜索树的根节点root，修剪的下限low和上限high。
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == NULL) return NULL;  // 如果根节点为空，递归结束，返回空指针。
        // 如果当前节点的值小于下限low，说明所有小于low的值都应该被修剪掉，递归修剪右子树。
        if (root->val < low) {
            return trimBST(root->right, low, high);
        }
        // 如果当前节点的值大于上限high，说明所有大于high的值都应该被修剪掉，递归修剪左子树。
        if (root->val > high) {
            return trimBST(root->left, low, high);
        }

        root->left = trimBST(root->left, low, high);// 递归修剪左子树，只保留在low和high之间的值。
        root->right = trimBST(root->right, low, high);// 递归修剪右子树，只保留在low和high之间的值。
        return root; // 返回当前节点，因为它的值在low和high之间，应该被保留。
    }
};

// 二、修剪二叉搜索树（迭代法）
class Solution {
public:
    // 定义一个名为trimBST的公共成员函数，接受两个参数：二叉搜索树的根节点root，以及修剪的区间边界L和R。
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root) return nullptr; // 如果根节点为空，直接返回空指针。

        // 处理头结点，让root移动到[L, R] 范围内。
        // 注意这里的处理方式是，如果当前节点的值小于L，就向右遍历；如果大于R，就向左遍历。
        while (root != nullptr && (root->val < L || root->val > R)) {
            if (root->val < L) root = root->right; // 如果当前节点的值小于L，向右子树移动。
            else root = root->left; // 如果当前节点的值大于R，向左子树移动。
        }
        TreeNode* cur = root; // 定义一个指针cur，用于遍历树。

        // 处理左孩子元素小于L的情况。
        // 这里通过不断向右遍历cur的左子树，直到找到一个值不小于L的节点或者没有左孩子为止。
        while (cur != nullptr) {
            while (cur->left && cur->left->val < L) {
                cur->left = cur->left->right; // 如果左孩子的值小于L，将左孩子指向其右孩子。
            }
            cur = cur->left; // 移动到当前节点的左孩子。
        }

        // 重新定义cur为root，因为我们需要处理右孩子大于R的情况。
        cur = root;
        // 处理右孩子大于R的情况。
        // 类似于处理左孩子，这里通过不断向左遍历cur的右子树，直到找到一个值不大于R的节点或者没有右孩子为止。
        while (cur != nullptr) {
            while (cur->right && cur->right->val > R) {
                cur->right = cur->right->left; // 如果右孩子的值大于R，将右孩子指向其左孩子。
            }
            cur = cur->right; // 移动到当前节点的右孩子。
        }

        return root; // 返回调整后的根节点。
    }
};

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

1.题目

Leetcode：第 108 题

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

示例 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] 都是高度平衡二叉搜索树。
2.解题思路

使用广度优先搜索来遍历有序数组，并根据数组中的元素构建对应的二叉搜索树。对于每个节点，
它都会计算出其左右子节点的区间，并创建子节点。然后，将子节点和对应的区间下标加入到队列中，以便后续处理。通过这种方式，可以确保每个节点都是按照有序数组的顺序被创建和连接的，从而构建出一个平衡的二叉搜索树。

3.实现代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 定义一个结构体TreeNode，用于表示二叉树的节点。
struct TreeNode {
    int val; // 存储节点的值。
    TreeNode* left; // 指向该节点左子树的指针。
    TreeNode* right; // 指向该节点右子树的指针。
    // TreeNode的构造函数，用于创建一个TreeNode实例。
    // 参数x是节点的值，left和right默认为NULL，表示没有左右子节点。
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//一、将有序数组转换为二叉搜索树（递归法）
class Solution {
public:
    // 定义一个名为traversal的成员函数，用于递归地将有序数组nums的一部分转换为二叉搜索树的子树。
    // 参数nums是输入的有序整数向量，left和right分别是当前子树在nums中的左右边界。
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return NULL; // 如果左边界大于右边界，说明当前子树为空，递归结束，返回空指针。
        int mid = left + ((right - left) / 2);// 计算当前子树的中间索引。
        TreeNode* root = new TreeNode(nums[mid]);// 创建一个新的TreeNode实例，其值为中间索引处的值。
        root->left = traversal(nums, left, mid - 1);// 递归地构建左子树，将当前子树的左边界和中间索引减一作为左子树的边界。
        root->right = traversal(nums, mid + 1, right);// 递归地构建右子树，将当前子树的中间索引加一和右边界作为右子树的边界。
        return root; // 返回新创建的TreeNode实例作为当前子树的根节点。
    }
    // 定义一个名为sortedArrayToBST的成员函数，用于将有序数组nums转换为二叉搜索树。
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        // 调用traversal函数，传入有序数组nums和数组的边界，初始化二叉搜索树。
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;// 返回构建好的二叉搜索树的根节点。
    }
};

//二、将有序数组转换为二叉搜索树（迭代法）
class Solution {
public:
    // 定义一个名为sortedArrayToBST的成员函数，用于将有序数组nums转换为二叉搜索树。
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return nullptr; // 如果输入数组为空，直接返回空指针。
        TreeNode* root = new TreeNode(0); // 创建一个新的TreeNode实例作为根节点，初始值为0。
        queue<TreeNode*> nodeQue; // 定义一个队列用于存放待遍历的节点。
        queue<int> leftQue;  // 定义一个队列用于存放左区间的下标。
        queue<int> rightQue;// 定义一个队列用于存放右区间的下标。
        nodeQue.push(root);// 将根节点入队。
        leftQue.push(0); // 将左区间下标初始位置0入队。
        rightQue.push(nums.size() - 1); // 将右区间下标初始位置（数组最后一个元素的索引）入队。

        // 广度优先搜索遍历数组和构建二叉搜索树。
        while (!nodeQue.empty()) {
            TreeNode* curNode = nodeQue.front();// 取出队列中的第一个节点。
            nodeQue.pop();
            int left = leftQue.front(); // 取出对应的左区间下标。
            leftQue.pop();
            int right = rightQue.front(); // 取出对应的右区间下标。
            rightQue.pop();
            int mid = left + ((right - left) / 2); // 计算当前节点的中间位置。
            curNode->val = nums[mid];// 将中间位置的元素赋值给当前节点。

            // 如果存在左子区间，则创建左子节点，并将其入队。
            if (left <= mid - 1) {
                curNode->left = new TreeNode(0);
                nodeQue.push(curNode->left);
                // 将左子区间的下标入队。
                leftQue.push(left);
                rightQue.push(mid - 1);
            }

            // 如果存在右子区间，则创建右子节点，并将其入队。
            if (right >= mid + 1) {
                curNode->right = new TreeNode(0);
                nodeQue.push(curNode->right);
                // 将右子区间的下标入队。
                leftQue.push(mid + 1);
                rightQue.push(right);
            }
        }
        return root;// 返回构建好的二叉搜索树的根节点。
    }
};

三、把二叉搜索树转换为累加树

1.题目

Leetcode：第 538 题

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（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]
2.解题思路

利用二叉搜索树的性质（左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值）
来将一个标准的二叉搜索树转换为一个累加树（每个节点的值是其所有左子孙节点值的累加加上其父节点的值）。通过进行二叉树的遍历，保证了节点的访问顺序为右-根-左。在访问每个节点时，都会将节点的值加上累加器 pre 的值，然后更新 pre 为当前节点的新值，以便在访问左子树时进行累加。

3.实现代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 定义一个结构体TreeNode，用于表示二叉树的节点。
struct TreeNode {
    int val; // 存储节点的值。
    TreeNode* left; // 指向该节点左子树的指针。
    TreeNode* right; // 指向该节点右子树的指针。
    // TreeNode的构造函数，用于创建一个TreeNode实例。
    // 参数x是节点的值，left和right默认为NULL，表示没有左右子节点。
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//一、把二叉搜索树转换为累加树（递归法）
class Solution {
public: 
    int pre = 0;// 定义一个名为pre的成员变量，用于在遍历过程中累加节点的值。
    // 定义一个名为traversal的成员函数，用于递归地访问二叉搜索树的节点。
    void traversal(TreeNode* cur) {
        if (cur == NULL) return; // 如果当前节点为空，递归结束，直接返回。
        traversal(cur->right); // 首先递归访问当前节点的右子树。
        cur->val += pre; // 将当前节点的值加上累加器pre的值。
        pre = cur->val; // 更新累加器pre的值为当前节点的新值。
        traversal(cur->left); // 然后递归访问当前节点的左子树。
    }

    // 定义一个名为convertBST的成员函数，用于将二叉搜索树转换为累加树。
    TreeNode* convertBST(TreeNode* root) {
        pre = 0; // 重置累加器pre的值为0。
        traversal(root); // 递归访问根节点，开始转换过程。
        return root; // 返回转换后的二叉搜索树的根节点。
    }
};

//二、把二叉搜索树转换为累加树（迭代法法）
class Solution {
public:
    int pre = 0;// 定义一个名为pre的成员变量，用于在遍历过程中累加节点的值。
    // 定义一个名为traversal的成员函数，用于递归地访问二叉搜索树的节点。
    void traversal(TreeNode* root) {
        stack<TreeNode*> st;// 定义一个栈st，用于存放二叉树的节点指针。
        TreeNode* cur = root; // 定义一个当前节点指针cur，初始指向根节点。

        // 当当前节点不为空，或者栈st不为空时，继续遍历。
        while (cur != NULL || !st.empty()) {
            // 如果当前节点不为空，将当前节点压入栈st，并将cur更新为当前节点的右子节点。
            if (cur != NULL) {
                st.push(cur);
                cur = cur->right;
            }

            // 如果当前节点为空，从栈st中弹出一个节点作为当前节点。
            else {
                // 弹出栈顶节点，并更新cur为该节点。
                cur = st.top();
                st.pop();
                
                cur->val += pre;// 将当前节点的值加上累加器pre的值。
     
                pre = cur->val;// 更新累加器pre的值为当前节点的新值。
                cur = cur->left;// 将cur更新为当前节点的左子节点，准备下一次循环。
            }
        }
    }
    // 定义一个名为convertBST的公共成员函数，用于将二叉搜索树转换为累加树。
    TreeNode* convertBST(TreeNode* root) {
        // 重置累加器pre的值为0。
        pre = 0;
        // 调用traversal函数，传入根节点，开始转换过程。
        traversal(root);
        // 返回转换后的二叉搜索树的根节点。
        return root;
    }
};

ps：以上皆是本人在探索算法旅途中的浅薄见解，诚挚地希望得到各位的宝贵意见与悉心指导，若有不足或谬误之处，还请多多指教。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/536320.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

huggingface连不上的解决方案

huggingface连不上的解决方案

不能科学上网的同学们, 代码中加载AI模型的时候, 会有下面的报错 We couldnt connect to https://huggingface.co to load this file, couldnt find it in the cached files and it looks like OFA-Sys/chinese-clip-vit-base-patch16 is not the path to a directory containi…
阅读更多...
Flask基于flask_login实现登录、验证码

Flask基于flask_login实现登录、验证码

flask_login 是一个 Flask 扩展&#xff0c;用于在 Flask web 应用中实现用户会话管理。它允许你跟踪哪些用户已经登录&#xff0c;并管理他们的登录状态。flask_login 提供了用户认证的基础结构&#xff0c;但具体的用户验证&#xff08;如用户名和密码检查&#xff09;和存储…
阅读更多...
3D Web轻量引擎HOOPS Communicator装配制造流程演示

3D Web轻量引擎HOOPS Communicator装配制造流程演示

介绍 该演示介绍了使用HOOPS Communicator的独特工作流程&#xff0c;该工作流程从零件列表中加载零件&#xff0c;并使用自定义配合操作符&#xff08;例如共线、同心和共面&#xff09;构建装配模型。该工作流程可用于各种行业&#xff0c;例如维护手册、工作指令或电子商务…
阅读更多...
Python中sort（）函数、sorted()函数的用法深入讲解（具体实例：蓝桥杯数位排序）

Python中sort（）函数、sorted()函数的用法深入讲解（具体实例：蓝桥杯数位排序）

前置知识&#xff1a; 可迭代对象的定义&#xff1a;可迭代对象是指可以被迭代或遍历的对象&#xff0c;即可以使用循环结构对其进行逐个访问的对象。 在Python中常见的可迭代对象有&#xff1a;列表(list)、元组&#xff08;tuple&#xff09;、字符串&#xff08;sting&…
阅读更多...
[CTF]使用浏览器firefox插件伪装IP地址

[CTF]使用浏览器firefox插件伪装IP地址

来源&#xff1a;https://jingyan.baidu.com/article/ab0b56306d9890c15bfa7d6a.html 浏览器想必是大家再熟悉不过的东东了&#xff0c;我们会经常使用它访问下载一些页面或文件。但是对于它的更深层次的功能可能就陌生了。比如说一些网站后台会记录我们的IP地址&#xff0c;假…
阅读更多...
【AI面试】FPN、PANet、SPP、ASPP、Adaptive feature pooling

【AI面试】FPN、PANet、SPP、ASPP、Adaptive feature pooling

经常可以看到各个论文发出来，加入的各种trick。这些改进点，一般都是在前人的基础上，进行了一些修改。比如FPN到PANet的改进，就是为了改进前者存在的一些问题。 这里就把这些trick，给汇集到一起，看看他们的发展历史，看看他们之间有什么区别，又是在哪些地方做的改进。这…
阅读更多...
OpenHarmony 3.2 Release版本Codec HDI适配过程

OpenHarmony 3.2 Release版本Codec HDI适配过程

简介 OpenHarmony Codec HDI&#xff08;Hardware Device Interface&#xff09;驱动框架基于 OpenMax 实现了视屏硬件编解码驱动&#xff0c;提供 Codec 基础能力接口供上层媒体服务调用&#xff0c;包括获取组件编解码能力、创建组件、参数设置、数据的轮转和控制、以及销毁…
阅读更多...
uniapp h5项目实现多选按钮/多选标签/多选框

uniapp h5项目实现多选按钮/多选标签/多选框

需求&#xff1a;实现简单多选功能&#xff0c;遍历数据&#xff0c;添加样式 1.效果图 2.以下代码粘贴到代码中&#xff0c;可直接运行&#xff0c;html代码 <view class"page index"><view class"list-box"><view v-for"(item,in…
阅读更多...
智能网络新纪元：机器学习赋能未来计算机网络高速发展

智能网络新纪元：机器学习赋能未来计算机网络高速发展

&#x1f9d1; 作者简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟,欢迎关注。提供嵌入式方向的学习指导…
阅读更多...
赋能技术 助锂制造|青软青之助力锂电检测行业数字化升级

赋能技术 助锂制造|青软青之助力锂电检测行业数字化升级

在全球范围内&#xff0c;新能源转型已成为时代的必然选择。随着“双碳”目标的深入推进&#xff0c;这一趋势愈发明显。而作为新能源领域的一颗璀璨明珠&#xff0c;锂电池的研发、产业链建设和技术创新&#xff0c;无疑是这场能源革命的核心所在。其产业链的日趋完善、技术的…
阅读更多...
企业培训系统私有化解决方案：PlayEdu

企业培训系统私有化解决方案：PlayEdu

PlayEdu&#xff1a;打造私有化的企业智慧教育平台&#xff0c;赋能全员高效成长&#xff01;- 精选真开源&#xff0c;释放新价值。 概览 随着企业不断发展及市场竞争加剧&#xff0c;内部培训的重要性日益凸显。然而&#xff0c;在实施过程中&#xff0c;如何确保培训内容与…
阅读更多...
2024个人动态线条导航HTML源码

2024个人动态线条导航HTML源码

源码介绍 2024个人导航HTML源码&#xff0c;源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面&#xff0c;重定向这个界面 源码下载 2024个人导航HTML源码
阅读更多...
进军俄罗斯市场，一站式Yandex广告开户与代运营服务

进军俄罗斯市场，一站式Yandex广告开户与代运营服务

俄罗斯作为欧洲最大的经济体之一&#xff0c;拥有庞大的消费者群体和独特的市场环境&#xff0c;成为了众多国际商家关注的焦点。要有效地触达这片潜力无限的市场&#xff0c;精准且高效的网络营销策略至关重要。利用Yandex——俄罗斯最大的搜索引擎与数字广告平台&#xff0c;…
阅读更多...
计算机网络-浏览器解析到URL对应的IP地址的时间

计算机网络-浏览器解析到URL对应的IP地址的时间

声明&#xff1a;原文转载链接出自&#xff1a; 哈工大Mooc——计算机网络&#xff1a;作业3 假设你在浏览某网页时点击了一个超链接&#xff0c;URL为“https://www.kicker.com.cn/index.html”&#xff0c;且该URL对应的IP地址在你的计算机上没有缓存&#xff1b;文件index…
阅读更多...
路由器如何端口映射到外网？

路由器如何端口映射到外网？

随着互联网的发展和普及&#xff0c;远程访问已经成为了现代社会的一个重要需求。在复杂的网络环境下&#xff0c;特别是涉及异地组网的情况下&#xff0c;实现远程访问变得更加困难。本文将介绍一种名为【天联】的组网产品&#xff0c;它可以解决复杂网络环境下的远程连接问题…
阅读更多...
最优算法100例之41-用两个栈实现队列

最优算法100例之41-用两个栈实现队列

专栏主页：计算机专业基础知识总结（适用于期末复习考研刷题求职面试）系列文章https://blog.csdn.net/seeker1994/category_12585732.html 题目描述 用两个栈实现队列 题解报告 stack<int> stack1; stack<int> stack2; void push(int node) {stack1.push(node);…
阅读更多...
极狐GitLab对接OAuth2实现SSO

极狐GitLab对接OAuth2实现SSO

本文作者&#xff1a;极狐(GitLab) 高级解决方案架构师 武让 GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署极狐GitLab。 企…
阅读更多...
windows停掉jenkins服务

windows停掉jenkins服务

在Windows系统中&#xff0c;如果你需要停止Jenkins服务&#xff0c; 使用服务管理器&#xff08;Service Manager&#xff09;: 打开“运行”对话框&#xff08;Win R&#xff09;&#xff0c;输入services.msc&#xff0c;然后回车。 在服务列表中找到“Jenkins”服务&am…
阅读更多...
网工基础协议——IP地址

网工基础协议——IP地址

IP地址的概念&#xff1a; IP 地址是我们进行TCP/IP通讯的基础&#xff0c;每个连接到网络上的计算机都必须有一个!P地址。我们目前使用的IP地址是32位的&#xff0c;通常以点分十进制表示。例如:192.168.0.181。IP地址的格式为: IP地址 网络地址 主机地址 或者 |P地址主机地…
阅读更多...
【Docker】docker快速安装部署fastdfs的镜像详细记录

【Docker】docker快速安装部署fastdfs的镜像详细记录

部署nacos的docker镜像 第一步&#xff1a; 获取fastdfs镜像1、查看镜像列表2、创建本地映射文件夹 第二步&#xff1a;运行镜像1.使用docker镜像构建tracker服务2.使用docker镜像构建Storage服务3.Storage服务中默认安装了Nginx服务4.如果需要修改storage则配置则进到以下目录…
阅读更多...
最新文章

Copyright @ 2022~2023