首页 > 其他分享 >LeetCode 538.把二叉搜索树转换成累加树

LeetCode 538.把二叉搜索树转换成累加树

时间:2023-04-14 23:35:55浏览次数:60  
标签:right TreeNode val 二叉 节点 null root LeetCode 538

1.题目:

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

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

节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。 注意:本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同


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

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/convert-bst-to-greater-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


2.代码:

/**
 * 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 {
    int sum;//定义全局变量,进行累加
    public TreeNode convertBST(TreeNode root) {
        sum = 0;//在这里设置初始值
        return serch(root);
       
    }
    public TreeNode serch(TreeNode root){
        if(root==null) return null;
        serch(root.right);//右
        sum+=root.val;//中  累加
        root.val=sum;//把这个累加到的值赋值给当前结点!!!
        serch(root.left);//左
        return root;

    }
}





标签:right,TreeNode,val,二叉,节点,null,root,LeetCode,538
From: https://blog.51cto.com/u_15806469/6191135

相关文章

  • #yyds干货盘点# LeetCode程序员面试金典:K 个一组翻转链表
    题目:给你链表的头节点head,每 k 个节点一组进行翻转,请你返回修改后的链表。k是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。 示例1:输入:head=[1,......
  • #yyds干货盘点# LeetCode面试题:最小覆盖子串
    1.简述:给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串,则返回空字符串""。 注意:对于t中重复字符,我们寻找的子字符串中该字符数量必须不少于t中该字符数量。如果s中存在这样的子串,我们保证它是唯一的答案。......
  • 树的遍历-二叉树
    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。输入格式:输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。输出格式:在一行中输出该树的层序遍......
  • 二叉树遍历(102.144.94.145)
    102.二叉树的层序遍历BPS/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(nullptr),right(nullptr){}*TreeNode(intx):val(x),left(nullptr)......
  • leetcode-1360-easy
    NumberofDaysBetweenTwoDatesWriteaprogramtocountthenumberofdaysbetweentwodates.Thetwodatesaregivenasstrings,theirformatisYYYY-MM-DDasshownintheexamples.Example1:Input:date1="2019-06-29",date2="201......
  • leetcode-844-easy
    BackspaceStringCompareGiventwostringssandt,returntrueiftheyareequalwhenbotharetypedintoemptytexteditors.'#'meansabackspacecharacter.Notethatafterbackspacinganemptytext,thetextwillcontinueempty.Example1:......
  • leetcode-830-easy
    PositionsofLargeGroupsInastringsoflowercaseletters,theselettersformconsecutivegroupsofthesamecharacter.Forexample,astringlikes="abbxxxxzyy"hasthegroups"a","bb","xxxx","z"......
  • leetcode-812-easy
    LargestTriangleAreaGivenanarrayofpointsontheX-Yplanepointswherepoints[i]=[xi,yi],returntheareaofthelargesttrianglethatcanbeformedbyanythreedifferentpoints.Answerswithin10-5oftheactualanswerwillbeaccepted.Exampl......
  • leetcode-944-easy
    DeleteColumnsToMakeSortedYouaregivenanarrayofnstringsstrs,allofthesamelength.Thestringscanbearrangedsuchthatthereisoneoneachline,makingagrid.Forexample,strs=["abc","bce","cae"]canb......
  • 代码随想录算法训练营Day01 | LeetCode704 二分查找、Leetcode27 移除元素
    今日学习的视频和文章代码随想录数组基础复习基础知识代码随想录二分查找代码随想录移除元素LeetCode704二分查找题目链接:704.二分查找-力扣(Leetcode)以前学二分查找的时候,真的一直搞不清楚怎么操作左边界和有边界,以及循环的终止条件是什么,总是自己慢慢调试出来,......