当前位置: 首页 > news >正文

计算机应用技术专业网站开发方向网页优化公司

计算机应用技术专业网站开发方向,网页优化公司,做gif动图的素材网站,东莞网站建设和制作538. 把二叉搜索树转换为累加树 文章目录 [538. 把二叉搜索树转换为累加树](https://leetcode.cn/problems/convert-bst-to-greater-tree/)一、题目二、题解方法一:递归(中序遍历与节点更新)方法二:反向中序遍历与累加更新&#x…

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

文章目录

      • [538. 把二叉搜索树转换为累加树](https://leetcode.cn/problems/convert-bst-to-greater-tree/)
        • 一、题目
        • 二、题解
          • 方法一:递归(中序遍历与节点更新)
          • 方法二:反向中序遍历与累加更新:更简洁的解法
          • 方法三:迭代(反向中序遍历)


一、题目

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

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

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

示例 1:

img

输入:[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]

提示:

  • 树中的节点数介于 0104 之间。
  • 每个节点的值介于 -104104 之间。
  • 树中的所有值 互不相同
  • 给定的树为二叉搜索树。

二、题解

方法一:递归(中序遍历与节点更新)

针对这个问题,我们可以考虑通过中序遍历来获取有序的节点值,然后从大到小更新节点的值,以满足累加树的要求。

算法思路

  1. 创建一个空的向量 array 用于存储中序遍历得到的有序节点值。

  2. 执行中序遍历函数 traversal_vec(root, array),该函数会将二叉搜索树的节点值按照从小到大的顺序存储在 array 中。

  3. array 的倒数第二个元素开始,将每个元素与其后一个元素相加,以便得到累加和。这一步保证了在累加树中,每个节点的值等于原树中大于或等于该节点值的所有节点值之和。

  4. 执行函数 traversal_res(root, array),该函数会将更新后的累加和值赋给二叉搜索树的每个节点。

  5. 返回更新后的二叉搜索树。

具体实现

以下是对每个步骤的详细实现:

class Solution {
public:int i = 0;// 中序遍历获取有序节点值并存储在array中void traversal_vec(TreeNode *root, vector<int> &array){if(root == nullptr) return;traversal_vec(root->left, array);array.push_back(root->val);traversal_vec(root->right, array);}// 更新节点值为累加和void traversal_res(TreeNode *root, vector<int>& array){if(root == nullptr) return;traversal_res(root->left, array);root->val = array[i++];traversal_res(root->right, array);}TreeNode* convertBST(TreeNode* root) {if(root == nullptr) return nullptr;vector<int> array;// 获取有序节点值traversal_vec(root, array);// 计算累加和for(int j = array.size() - 2; j >= 0; j--){array[j] += array[j+1];}// 更新节点值为累加和traversal_res(root, array);return root;}
};

或者将i作为参数传入traversal_res()也行:

class Solution {
public:void traversal_vec(TreeNode *root, vector<int> &array) {if (root == nullptr) return;traversal_vec(root->left, array);array.push_back(root->val);traversal_vec(root->right, array);}int traversal_res(TreeNode *root, int i, const vector<int> &array) {if (root == nullptr) return i;i = traversal_res(root->left, i, array);root->val = array[i];i++;i = traversal_res(root->right, i, array);return i;}TreeNode* convertBST(TreeNode* root) {if (root == nullptr) return nullptr;vector<int> array;traversal_vec(root, array);for (int j = array.size() - 2; j >= 0; j--) {array[j] += array[j + 1];}traversal_res(root, 0, array);return root;}
};

算法分析

  • 时间复杂度:算法的时间复杂度主要由两个部分构成:中序遍历和更新节点值。中序遍历需要访问每个节点一次,而更新节点值也需要访问每个节点一次。因此,算法的时间复杂度为 O(N),其中 N 是节点的数量。

  • 空间复杂度:算法的空间复杂度主要由中序遍历时存储节点值的数组 array 所占用的空间。在最坏的情况下,数组的大小为 N,因此空间复杂度为 O(N)。除此之外,递归调用栈也会占用一些空间,但是在二叉搜索树的情况下,递归调用栈的最大深度不会超过树的高度,因此额外空间的使用不会超过 O(log N)。

方法二:反向中序遍历与累加更新:更简洁的解法

算法思路

这个算法采用了一种不同的方法来实现二叉搜索树到累加树的转换。通过反向中序遍历(从右子树到左子树),我们可以更方便地得到大于当前节点值的节点值之和,然后直接更新节点值,从而获得累加树。

具体实现

class Solution {
public:// 反向中序遍历并更新节点值void convertBSTHelper(TreeNode* root, int& sum) {if(root == nullptr) return;convertBSTHelper(root->right, sum); // 先处理右子树sum += root->val; // 更新累加和root->val = sum; // 更新节点值convertBSTHelper(root->left, sum); // 处理左子树}TreeNode* convertBST(TreeNode* root) {if(root == nullptr) return nullptr;int sum = 0;convertBSTHelper(root, sum);return root;}
};

算法分析

  • 时间复杂度:算法的时间复杂度主要由中序遍历和更新节点值组成。每个节点都会被访问一次且只访问一次,因此时间复杂度为 O(N),其中 N 是节点的数量。
  • 空间复杂度:算法的空间复杂度由递归调用栈所占用的空间决定。在二叉搜索树的情况下,递归调用栈的最大深度不会超过树的高度,因此额外空间的使用不会超过 O(log N)。
方法三:迭代(反向中序遍历)

算法思路

这个算法采用了反向中序遍历的方式,通过栈来实现,来构建累加树。遍历的过程中,我们从最大值开始,逐步向较小值移动,同时将大于等于当前节点值的所有节点值累加起来,然后将该累加值赋予当前节点,最终构建出累加树。

具体实现

class Solution {
private:int previousValue; // 记录前一个节点的值// 反向中序遍历并更新节点值void reverseInorderTraversal(TreeNode* root) {stack<TreeNode*> nodeStack;TreeNode* current = root;while (current != nullptr || !nodeStack.empty()) {if (current != nullptr) {nodeStack.push(current);current = current->right; // 右子树} else {current = nodeStack.top(); // 弹出栈顶节点nodeStack.pop();// 更新节点值current->val += previousValue;previousValue = current->val;current = current->left; // 左子树}}}public:TreeNode* convertBST(TreeNode* root) {previousValue = 0; // 初始化前一个节点的值reverseInorderTraversal(root); // 反向中序遍历更新节点值return root;}
};

算法分析

  • 时间复杂度:算法的时间复杂度主要由反向中序遍历过程构成。每个节点会被访问一次且只访问一次,因此时间复杂度为 O(N),其中 N 是节点的数量。

  • 空间复杂度:算法的空间复杂度由栈所占用的空间决定。在最坏情况下,栈的大小可能达到树的高度,即 O(log N)。

http://www.ds6.com.cn/news/537.html

相关文章:

  • 做任务挣钱网站竞价推广运营
  • 盱眙在仕德伟做网站的有几家重庆自动seo
  • p2p网站建设百度快速排名点击器
  • 外贸网站seo招聘推广普通话奋进新征程
  • 官方网站想反应问题不弄应该怎么做营销案例100例小故事及感悟
  • 网站的建设方案怎么写百度seo新站优化
  • photoshop 做网站免费设计模板网站
  • 企业网站模板下载哪里seo技术培训课程
  • 长安外贸网站建设公司品牌公关
  • 广州注册公司代理记账杭州优化公司哪家好
  • 成都网站空间创新互联长沙市seo百度关键词
  • 免费营销型网站seo实战培训学校
  • 嘉兴网站建设维护小程序seo
  • 网站标题堆砌关键词百度指数app
  • 基于java的小说网站开发微信推广引流加精准客户
  • 德州哪个做网站做得好品牌营销案例分析
  • 建设一个商务网站的步骤seo关键词怎么填
  • 做外贸的人常用的网站新手怎么做电商运营
  • 查询优惠券的网站如何做中国网站排名网官网
  • c 语言做网站不错宁波seo公司
  • 会员发布网站建设宁波关键词优化时间
  • 国内有做网游评测的网站么郑州seo技术服务顾问
  • 网站建设有哪些渠道企业qq一年多少费用
  • 网站提升权重广东seo排名
  • 郑州网站建设 郑州网站设计青岛网站优化公司
  • 有哪些比较好的做ppt好的网站可以进入任何网站的浏览器
  • mvc做网站前台代码怎么做好市场宣传和推广
  • 专业的营销型网站建设公司新闻热点素材
  • 免费网站建设哪个好 - 百度顺德搜索seo网络推广
  • 如何建设网站山东济南兴田德润官网百度首页关键词优化