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

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

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

题目描述

给定一个二叉搜索树 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);}
}

这篇关于力扣1038. 从二叉搜索树到更大和树（java，树的中序遍历解法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---