33_把二叉搜索树转换为累加树

简介: 33_把二叉搜索树转换为累加树

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

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

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

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

注意:本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 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 {
   int sum = 0;
   public TreeNode convertBST(TreeNode root) {
       convertBST1(root);
       return root;
   }
   // 按右中左顺序遍历,累加即可
   public void convertBST1(TreeNode root) {
       if (root == null)
           return;
       convertBST(root.right);
       sum += root.val;
       root.val = sum;
       convertBST(root.left);
   }
}
//leetcode submit region end(Prohibit modification and deletion)

迭代法

class Solution {
    //DFS iteration统一迭代法
    public TreeNode convertBST(TreeNode root) {
        int pre = 0;
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) 
            return null;
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode curr = stack.peek();
            //curr!=null的情况,只负责存node到stack中
            if (curr != null) {
                stack.pop();
                if (curr.left != null)  //左
                    stack.add(curr.left);
                stack.add(curr); //中
                stack.add(null);
               if(curr.right != null)      //右
                    stack.add(curr.right);
            }else{
            //curr == null的状况,只负责做单层逻辑
                stack.pop();
                TreeNode temp = stack.pop();
                temp.val += pre;
                pre = temp.val;
            }
        }
        return root;
    }
}
相关文章
|
前端开发 JavaScript 测试技术
30个前端和设计必备网站,让你的工作更轻松!
30个前端和设计必备网站,让你的工作更轻松!
3219 1
|
8月前
|
弹性计算 人工智能 安全
2026年阿里云开年焕新特惠:多款云服务器限时低价,免费试用最高享660元额度
2026年初,阿里云推出“开年焕新”限时活动:轻量服务器低至68元/年,ECS经济型99元/年,第9代企业实例享6.4折;每日秒杀、最高660元免费试用、建站套餐109元起,另赠安全防护与备份权益,助力个人开发者及企业低成本上云与AI创新。
1041 1
|
3月前
|
自然语言处理 API 数据库
突破检索失真:高精度 RAG 向量相似度动态截断与分流实操
机械式固定 Top-K 检索在面对知识库外提问时,极易强行返回低相似度“伪相关”切块,诱发严重的模型幻觉。 本文深入探讨“高精度 RAG 向量检索相似度阈值截断设置”,解析余弦相似度与欧氏距离的度量基准,并提出硬阈值、动态落差、软硬双阈值分流与混合融合截断四种进阶策略。文章还提供了基于黄金测试集与 F1-Score 的科学阈值标定方法,助力系统筑牢防线、杜绝胡说八道。
396 0
|
11月前
|
消息中间件 人工智能 运维
别让"我觉得"毁了架构:用这条指令让AI做你的技术选型审计员
技术选型往往受限于主观偏见和认知盲区。本文提供了一套“技术选型分析”AI指令,将大模型化身为客观的架构审计员,通过多维度评分和风险评估,帮助开发者从“经验驱动”转向“证据驱动”,做出经得起时间考验的技术决策。
507 5
3月前
|
人工智能 DataWorks 监控
DataWorks AI助理实践:推送报警至钉钉群并准确@责任人
本文介绍如何为DataWorksAI助理配置阿里云账号(空间成员)与钉钉的账号映射,实现报警时自动在钉钉群精准@责任人。通过配置监控报警、建立RAM用户与钉钉账号映射、接入Webhook及创建定时巡检任务,确保报警消息准确触达,提升运维响应效率。
563 0
|
弹性计算 运维 安全
【阿里云安全小贴士】创建ECS后,这3个配置千万别漏过
为保障阿里云ECS安全,建议完成三项基础配置:使用安全的登录方式、启用免费主机安全防护、设置自动备份策略。操作简单,配置之后可显著提升系统安全性与业务连续性。
【阿里云安全小贴士】创建ECS后,这3个配置千万别漏过
|
7月前
|
弹性计算
如何查询自己的阿里云账户是新用户还是老用户?
阿里云新用户指无任何收费云产品购买记录的实名认证用户(含试用未付费者);老用户则已有付费订单。同一证件下多账号共享唯一新用户资格。本文详解判定标准与自查步骤,助力大家精准锁定优惠权益。
988 9
|
8月前
|
机器学习/深度学习 监控 安全
再也不怕局部拍屏泄露:一项能抗部分屏幕拍摄的溯源黑科技来了(第10期)
针对“拍屏截取局部”导致传统水印失效的难题,合肥高维数据与中科大联合研发《抗部分屏幕拍摄的溯源水印方法》,首创结构化水印+双阶段深度学习增强技术,支持畸变、裁剪、摩尔纹等复杂干扰下的高鲁棒溯源,已应用于政企保密、版权保护与司法取证等领域。(239字)
910 2
|
11月前
|
运维 安全 网络安全
1分钟搞定!WNMP一键包:IP+SSL双加密+WebDAV网盘+密钥登录,安全不折腾
开发者自研的WNMP一键包,把「安全刚需」做到极致――IP绑定SSL加密、WebDAV加密网盘、SSH密钥登录三大核心功能一键拉满,配合Nginx+PHP+MariaDB生产级环境,512M内存就能跑,开发者/中小站长/私有化部署直接闭眼冲!
|
8月前
|
安全 Linux 开发者
拒绝平庸:从零电平到操作系统,BootLoader硬核全景解析
本文深入解析BootLoader——嵌入式系统启动的“硅基唤醒者”。从硬件上电瞬间的CPU懵懂状态讲起,详述其初始化内存、搬运内核、设置异常向量、安抚看门狗、地址重定位等核心使命,并对比U-Boot、Barebox、LK等主流方案,展现其在驱动模型、网络启动、安全验证等高级特性上的强大能力。(239字)
1078 1