力扣题538把二叉搜索树转换为累加树
发布日期:2022-03-04 11:48:20
浏览次数:6
分类:技术文章
本文共 1174 字,大约阅读时间需要 3 分钟。
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(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]1.因为是二叉搜索树,中序遍历就是按照值从小到大进行排列,其逆序就是从大到小进行排列,因此对中序遍历的逆序结果进行累加即可。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { int num = 0;//用一个全局变量存储累加值 public TreeNode convertBST(TreeNode root) { if (root == null) { return null; } //按照中序遍历的逆序右根左调整每个节点的值 convertBST(root.right);//右子树 root.val = root.val + num;//改变当前节点的值 num = root.val;//更新累加值 convertBST(root.left);//左子树 return root; }}
题源:
转载地址:https://blog.csdn.net/xxyneymar/article/details/122284635 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月14日 04时45分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
容易被忽略的陌生人社交礼仪!
2021-06-28
DbHelper
2021-06-28
SqlHelper
2021-06-28
ArticleDAL
2021-06-28
git 终端显示中文乱码
2021-06-28
关于java.lang.IllegalStateException: getOutputStream() has already been called for this response求解
2021-06-28
oracle 10.2.0.1.0 误删除数据文件 后的处理方法
2021-06-28
JPA 默认值配置
2021-06-28
myeclipse 的 maven工程报错或pom.xml头报错解决办法
2021-06-28
反向Ajax,第2部分:WebSocket
2019-04-25
反向Ajax,第1部分:Comet介绍
2019-04-25
反向Ajax,第3部分:Web服务器和Socket.IO
2019-04-25
反向Ajax,第4部分:Atmosphere和CometD
2019-04-25
反向Ajax,第5部分:事件驱动的Web开发
2019-04-25
Servlet3.0新特性&动态代理
2019-04-25
servlet3 实现请求异步处理
2019-04-25
java线程管理利器:java.util.current的用法举例
2019-04-25
native2ascii.exe的使用
2019-04-25
docker-machine的安装
2019-04-25
用docker-machine创建虚拟主机
2019-04-25