LeetCode如何把二叉搜索树转换为累加树
发表于:2024-11-14 作者:千家信息网编辑
千家信息网最后更新 2024年11月14日,这篇文章主要介绍了LeetCode如何把二叉搜索树转换为累加树,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。1,问题简述给出二叉 搜索
千家信息网最后更新 2024年11月14日LeetCode如何把二叉搜索树转换为累加树
这篇文章主要介绍了LeetCode如何把二叉搜索树转换为累加树,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
1,问题简述
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。提醒一下,二叉搜索树满足下列约束条件:节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。
2,示例
输入:[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 和 100 之间。
每个节点的值介于 0 和 100 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
3,题解思路
写了最基本的思路来解决,先统计二叉树的节点数据,然后根据题目的已知条件进行计算,数据赋值就可以了
4,题解程序
import java.util.ArrayList;
import java.util.List;
public class ConvertBSTTest {
static List
list = new ArrayList<>();
public static void main(String[] args) {
TreeNode t1 = new TreeNode(4);
TreeNode t2 = new TreeNode(1);
TreeNode t3 = new TreeNode(6);
TreeNode t4 = new TreeNode(0);
TreeNode t5 = new TreeNode(2);
TreeNode t6 = new TreeNode(5);
TreeNode t7 = new TreeNode(7);
TreeNode t8 = new TreeNode(3);
TreeNode t9 = new TreeNode(8);
t1.left = t2;
t1.right = t3;
t2.left = t4;
t2.right = t5;
t3.left = t6;
t3.right = t7;
t5.right = t8;
t7.right = t9;
TreeNode treeNode = convertBST(t1);
System.out.println("treeNode = " + treeNode);
}
public static TreeNode convertBST(TreeNode root) {
if (root == null) {
return null;
}
if (list.size() == 0) {
dfs(root);
}
Integer compute = compute(root.val);
root.val = compute;
if (root.left != null) {
convertBST(root.left);
}
if (root.right != null) {
convertBST(root.right);
}
return root;
}
private static Integer compute(Integer val) {
int sum = 0;
for (int num : list) {
if (num > val) {
sum += num;
}
}
sum += val;
return sum;
}
private static void dfs(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
dfs(root.left);
}
list.add(root.val);
if (root.right != null) {
dfs(root.right);
}
}
}
5,题解程序图片版
6
感谢你能够认真阅读完这篇文章,希望小编分享的"LeetCode如何把二叉搜索树转换为累加树"这篇文章对大家有帮助,同时也希望大家多多支持,关注行业资讯频道,更多相关知识等着你来学习!
节点
搜索
示例
篇文章
输入
输出
题解
子树
相同
之间
思路
数据
条件
程序
之和
价值
兴趣
同时
图片
更多
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
python 数据库访问队列
香港服务器 试用
陕西超频服务器咨询报价
软件开发常见面试问题
国家软件开发大赛
负载均衡服务器同步数据
规则引擎开启sql服务器
java数据库连接监控
vs连接mysql数据库
浙江软件开发服务参考价格
查看数据库监听状态
南京学编程软件开发
服务器远程连接密码破解工具
北京本地软件开发价格大全
北美软件开发环境
淘宝定时抢单软件开发
mc 1.0.3 服务器
数据库加解密
电脑版微信数据库如何查看
相城区管理软件开发质量
微信登录服务器异常怎么办
聚嘉网络技术有限公司怎么样
重庆应用软件开发收费报价表
数据库中平均分如何表示
手机网站二级服务器
数据库虚拟个人信息
司法局网络安全知识宣传简报
安徽网络安全非标机箱上哪找
服务器显示网络没响应
服务器系统正版和盗版区分