力扣1038. 从二叉搜索树到更大和树（java，树的中序遍历解法）

本文主要是介绍力扣1038. 从二叉搜索树到更大和树（java，树的中序遍历解法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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)$

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);}
}