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

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

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]

提示:

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/convert-bst-to-greater-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、思路分析:

二叉搜索树满足下列约束条件:

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
题目意思是先更新右子树值,再更新自己的值,再更新左子树的值
不难想到树的中序遍历 -> 左根右
但是可以看到这与题目需要的右根左正好相反,那么我们就按题目给定要求,调整一下中序遍历遍历的顺序,将其反向,反向中序遍历

三、AC 代码:

class Solution {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}
AI 代码解读

四、总结:

image.png

掘友们,解题不易,留下个赞或评论再走吧!谢啦~ 💐

希望对你有帮助

期待下次再见~

目录
打赏
0
0
0
0
4
分享
相关文章
纯前端打造一个简易实时预览的markdown编辑器
先下载https://github.com/markedjs/marked和https://github.com/ajaxorg/ace-builds/插件,还有JQuery也是不可少的 --在线markdown编辑器参考,https://www.
1738 0
【alibaba/jvm-sandbox#03】JavaAgent 修改字节码的机制
开发者一般采用建立一个 Agent 的方式来使用 JVMTI,使用 JVMTI 一个基本的方式就是设置回调函数,在回调函数体内,可以 获取各种各样的VM级信息,甚至控制VM行为,如类加载时修改类
427 0
关于JWT鉴权安全问题
JSON Web Token(JWT https://jwt.io )是一种跨域身份验证解决方案,其主要认证原理是提供一个可信签名,利用存在客户端的secret_key将明文的鉴权数据做一个签名,用于跨域校验权限的合法性。
关于JWT鉴权安全问题
攻防:如何防止动态hook绕过jni签名校验
攻 我们知道jni校验签名也不可靠,可以被动态hook绕过。代码如下:
483 0
Java如何支持函数式编程?
Java是面向对象的语言,无法直接调用一个函数。Java 8开始,引入了函数式编程接口与Lambda表达式,便于开发者写出更少更优雅的代码。什么是函数式编程?函数式编程的特点是什么?本文通过代码实例,从Stream类、Lambda表达式和函数接口这三个语法概念来分享Java对函数式编程的支持。
11135 0
Java如何支持函数式编程?
Jvm-Sandbox源码分析--增强目标类
在前两篇文章Jvm-Sandbox源码分析--启动简析和Jvm-Sandbox源码分析--启动时加载模块中我们分析了jvm-sandbox启动及启动时加载模块的过程,这一篇我们来看一下如何使用模块增强目标类的流程。
4615 0
IDEA安装插件 之 使用本地下载的jar包安装
IDEA安装插件 之 使用本地下载的jar包安装
820 0
IDEA安装插件 之 使用本地下载的jar包安装

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等