力扣1038. 从二叉搜索树到更大和树(java,树的中序遍历解法)

news/2024/4/25 20:20:17

Problem: 1038. 从二叉搜索树到更大和树

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

给定一个二叉搜索树 root (BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

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

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

示例 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]

提示:

树中的节点数在 [1, 100] 范围内。
0 <= Node.val <= 100
树中的所有值均 不重复 。

思路

我们易得到对于一个二叉搜索树,若我们按右-根-左的顺序递归中序遍历可以的得到一个递减的节点值序列,我们再利用一个变量在的过程中将当前的节点值加到变量中再将当前节点值修改为当前的变量值。

解题方法

1.记录一个成员变量sum用于记录中序遍历序列的累加值
2.按右-根-左的顺序递归中序遍历,递归结束条件为root == null
3.在归的过程中让sum加上当前节点值,再让sum赋值给当前节点值

复杂度

  • 时间复杂度:

O ( n ) O(n) O(n)

  • 空间复杂度:

O ( n ) O(n) O(n)

Code


/*** 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 {//Time Complexity: O(n)//Space Complexity: O(n)int sum = 0;public TreeNode bstToGst(TreeNode root) {resInorder(root);return root;}private void resInorder(TreeNode root) {if (root == null) return;resInorder(root.right);sum += root.val;root.val = sum;resInorder(root.left);}
}

https://www.xjx100.cn/news/3092672.html

相关文章

抽象工厂设计模式是什么?什么是 Abstract Factory 抽象工厂设计模式?Python 抽象工厂设计模式示例代码

什么是 Abstract Factory 抽象工厂设计模式&#xff1f; 抽象工厂设计模式是一种创建型设计模式&#xff0c;旨在提供一个创建一系列相关或相互依赖对象的接口&#xff0c;而无需指定其具体类。它允许客户端使用抽象的接口创建一组相关对象&#xff0c;而无需关注实际的对象实…

C++刷题 -- 二分查找

C刷题 – 二分查找 文章目录 C刷题 -- 二分查找一、原理二、例题1.二分查找2.使用二分查找确定target左右边界3.x的平方根 一、原理 条件&#xff1a;数组为有序数组&#xff0c;数组中无重复元素&#xff0c;因为一旦有重复元素&#xff0c;使用二分查找法返回的元素下标可能…

相机机模组需求示例

产品需求名称摄像头采集图片数据补充说明产品需求描述 As&#xff1a;用户 I want to&#xff1a;通过相机模组获取到自定义格式图片数据&#xff0c;要求包括&#xff1a; 1、支持多种场景&#xff0c;如&#xff1a;手持相机拍摄舌苔 2、支持图片分辨率至少达到1920X1080 3、…

【Python 千题 —— 基础篇】2 的 N 次方

题目描述 题目描述 2 的 N 次方。输入一个整数 N&#xff0c;使用 for 循环计算 2 的 N 次方的值。 输入描述 输入一个整数值 N。 输出描述 输出 2 的 N 次方的值。 示例 示例 ① 输入&#xff1a; 20输出&#xff1a; 请输入一个整数 N: 20 2 的 20 次方的值是: 10…

UE必学系列(基础篇完结)

导语&#xff1a; UE必须系列基础篇完结&#xff0c;敬请期待进阶篇 基础篇文章&#xff1a;在掌握了UE4基础操作&#xff0c;并且能上手做一些项目之后&#xff0c;对UE4知识进行更完善的知识体系学习。主要是把学习视频链接汇总&#xff0c;主要学习思路是 优先官方视频和官…

gitlab图形化界面使用

gitlab使用 创建用户 上面是创建用户基本操作 修改密码 创建组 给组添加用户 创建项目 选择空白项目 退出root用户&#xff0c;切换其他用户 在服务器上创建ssh密钥 使用ssh-ketgen 命令 新服务器上创建的 [rootgitlab ~]# ssh-keygen Generating public/private rsa key …

Redis从入门到精通(二)- 入门篇

文章目录 0. 前言1. 入门篇[【入门篇】1.1 redis 基础数据类型详解和示例](https://icepip.blog.csdn.net/article/details/134438573)[【入门篇】1.2 Redis 客户端之 Jedis 详解和示例](https://icepip.blog.csdn.net/article/details/134440061)[【入门篇】1.3 redis客户端之…

链路聚合-静态和动态区别

链路聚合之动静态聚合方式 链路聚合组是由一组相同速率、以全双工方式工作的网口组成。 1、动态聚合&#xff1a; 动态聚合对接的双方通过交互LACP(链路聚合控制协议)协议报文&#xff0c;来协商聚合对接。 优点&#xff1a;对接双方相互交互端口状态信息&#xff0c;使端口…