首页 > 其他分享 >538. Convert BST to Greater Tree刷题笔记

538. Convert BST to Greater Tree刷题笔记

时间:2023-05-26 22:05:24浏览次数:50  
标签:node Convert Greater val BST self None root left


问题描述 第一次没做出来,主要问题还是出在递归上
pycharm代码

class Node(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 树生成代码
def generate_tree(vals):
    if len(vals) == 0:
        return None
    que = [] # 定义队列
    fill_left = True # 由于无法通过是否为 None 来判断该节点的左儿子是否可以填充,用一个记号判断是否需要填充左节点
    for val in vals:
        node = Node(val) if val is not None else None # 非空值返回节点类,否则返回 None
        if len(que)==0:
            root = node # 队列为空的话,用 root 记录根结点,用来返回
            que.append(node)
        elif fill_left:
            que[0].left = node
            fill_left = False # 填充过左儿子后,改变记号状态
            if node: # 非 None 值才进入队列
                que.append(node)
        else:
            que[0].right = node
            if node:
                que.append(node)
            que.pop(0) # 填充完右儿子,弹出节点
            fill_left = True #
    return root

root = generate_tree([4,1,6,0,2,5,7,None,None,None,3,None,None,None,8])


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.sum = 0

    def convertBST(self, root):
        if root:
            self.convertBST(root.right)
            self.sum += root.val
            root.val = self.sum
            self.convertBST(root.left)
        return root
print(Solution().convertBST(root))
print("hi")

运行结果:

538. Convert BST to Greater Tree刷题笔记_递归


标签:node,Convert,Greater,val,BST,self,None,root,left
From: https://blog.51cto.com/u_16131692/6359363

相关文章

  • 647. Palindromic Substrings刷题笔记
    用动态规划可以做,应该可以优化为只有两个表,而且不用每次res都加classSolution:defcountSubstrings(self,s:str)->int:n=len(s)dp=[[0]*nfor_inrange(n)]res=0foriinrange(n-1,-1,-1):forji......
  • HttpMessageConverter<T>的了解
    消息转换器的具体工作机制示意图 SpringMVC处理json底层就是依靠HttpMessageConverter来实现的。前台发来一个请求报文,根据请求报文的类型来选择一个实现了HttpinputMessage的接口的类来封装信息,然后根据请求头的Accept属性来选择对应的实现了HttpMessageConverter的接口的类......
  • webstore报 ESLint: Expected space or tab after '//' in comment.(spaced-comment)
    webstore报:ESLint:Expectedspaceortabafter'//'incomment.(spaced-comment) 解决方法:禁用ESLINT......
  • webstore忽略指定的文件夹显示
    ......
  • AQS源码解读----AbstractQueuedSynchronizer
    36packagecn.com.pep;37importjava.util.concurrent.TimeUnit;38importjava.util.concurrent.locks.AbstractOwnableSynchronizer;39importjava.util.concurrent.locks.Condition;40importjava.util.concurrent.locks.LockSupport;41importjava.......
  • Caused by: io.netty.channel.AbstractChannel$AnnotatedConnectException: Connectio
    现象:今天在启动项目时,本项目使用了Elasticsearch服务,发现后台报这个错误:Causedby:io.netty.channel.AbstractChannel$AnnotatedConnectException:Connectionrefused:nofurtherinformation:/127.0.0.1:9300错误信息提示如下图:原因:本项目使用了Elasticsearch搜索服务,而报错信......
  • bst中序-leetcode230二叉搜索树第k个元素
    给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从1开始计数)。示例1:输入:root=[3,1,4,null,2],k=1输出:1示例2:输入:root=[5,3,6,2,4,null,null,1],k=3输出:3提示:树中的节点数为 n 。1<=k<=n<=1040<=Node.val<......
  • JAVA 截取字符串的三种方法 subString,StringUtils,split
    JAVA截取字符串的三种方法subString,StringUtils,split主要有以下几种方法:1、通过subString()方法来进行字符串截取(最常用)2、通过StringUtils提供的方法3、split()+正则表达式来进行截取 1、通过subString()方法来进行字符串截取,返回字符串中的子字符串,在java中有两种用......
  • Ubuntu 18.04 BST -- Docker 命令
    一、查看DockerIP进入Docker  l@l-VirtualBox:~/sdk-a1000-docker/BST-HS-Linux-SDK-<Version>/sdk/SDK-Docker-fad-<Version>$sudo./run_docker.sha1000b-sdk-fad-<Version>...sdkdockerimg:a1000b-sdk-fad-2.3.0.4.tarstartloadsdkversionima......
  • C#中BitConverter.ToUInt16、BitConverter.ToUInt32原理与用法详解
    一、基础知识a、1字节=8位(1Byte=8bit) 二进制表示:11111111 十进制表示:255计算机内部约定用多少字节来规范数值,比如红绿蓝三色在计算机中只分配了一个字节,一个字节有八位,每一位只能储存1或0,计算机只认识二进制(0与1),所以就是2的八次方,计算机中约定从0开始计数,所......