当前位置:网站首页>二叉树创建 & 遍历
二叉树创建 & 遍历
2022-07-06 07:40:00 【王吉吉丫】
层次创建
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = None
self.right = None
def creatTree(nodeList):
if nodeList[0] == None: return None
head = TreeNode(nodeList[0])
nodes = [head] # 用于存放树中的节点,每生成一个节点就将其放入该列表中,此处将根节点存入。
j = 1 # 创建变量j用于nodeList中元素的索引,初始为1.因为第0个元素已经创建根节点了。
for node in nodes: # 依次取出Nodes列表中的节点,对其创建左子节点和右子节点
if node != None:
node.left = (TreeNode(nodeList[j])) if nodeList[j] != None else None
nodes.append(node.left) # 将新建的节点加入Nodes数组,使其在for循环中可以继续为其添加子节点
j += 1
if j == len(nodeList): # 如果与nodeList值相等说明全部节点已经添加完毕了,直接返回head根节点就完成了树的建立
return head
node.right = (TreeNode(nodeList[j])) if nodeList[j] != None else None
j += 1
nodes.append(node.right)
if j == len(nodeList):
return head
a = [1,2,3,4,None,6,7]
a = creatTree(a)
# 使用:返回二叉树最长路径,Leecode 124
class Solution:
def __init__(self):
self.maxSum = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def maxGain(node):
if not node:
return 0
leftGain = max(maxGain(node.left), 0)
rightGain = max(maxGain(node.right), 0)
priceNewpath = node.val + leftGain + rightGain
self.maxSum = max(self.maxSum, priceNewpath)
return node.val + max(leftGain, rightGain)
maxGain(root)
return self.maxSum
s = Solution()
s.maxPathSum(a)
Continue......
边栏推荐
- Excel的相关操作
- [dictionary tree] [trie] p3879 [tjoi2010] reading comprehension
- [MySQL learning notes 29] trigger
- C # create database connection object SQLite database
- 【mysql学习笔记30】锁(非教程)
- Sharing of source code anti disclosure scheme under burning scenario
- After the hot update of uniapp, "mismatched versions may cause application exceptions" causes and Solutions
- [非线性控制理论]9_非线性控制理论串讲
- Type of data in energy dashboard
- [1. Delphi foundation] 1 Introduction to Delphi Programming
猜你喜欢
[window] when the Microsoft Store is deleted locally, how to reinstall it in three steps
DataX self check error /datax/plugin/reader/_ drdsreader/plugin. Json] does not exist
[CF Gym101196-I] Waif Until Dark 网络最大流
烧录场景下的源代码防泄密方案分享
Opencv learning notes 8 -- answer sheet recognition
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
学go之路(一)go的基本介绍到第一个helloworld
861. Score after flipping the matrix
octomap averageNodeColor函数说明
随机推荐
Apache middleware vulnerability recurrence
软件开发的一点随记
C # create database connection object SQLite database
Select all the lines with a symbol in word and change them to titles
Bit operation XOR
继电反馈PID控制器参数自整定
【MySQL学习笔记32】mvcc
Openjudge noi 2.1 1749: Digital Square
Comparison of usage scenarios and implementations of extensions, equal, and like in TS type Gymnastics
NiO programming introduction
【Redis】NoSQL数据库和redis简介
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
数字经济时代,如何保障安全?
Ble of Jerry [chapter]
[MySQL learning notes 29] trigger
Linked list interview questions (Graphic explanation)
TS 类型体操 之 循环中的键值判断,as 关键字使用
学go之路(二)基本类型及变量、常量
TS 类型体操 之 extends,Equal,Alike 使用场景和实现对比
【mysql学习笔记30】锁(非教程)