网站设置域名,四川手机网站设计方案,世界建筑网,seo研究协会网是干什么的Problem: 1038. 从二叉搜索树到更大和树 文章目录 题目描述思路解题方法复杂度Code 题目描述
给定一个二叉搜索树 root (BST)#xff0c;请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
提醒一下#xff0c; 二叉搜索树 满足下列约束条件#xff… 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);}
}
