我在用Python做上面的leetcode问题。我通常会在jupyter笔记本上解决问题,然后在完成后将其复制并粘贴到leetcode解决方案框中。然而,我对这个问题有异议。
给定二进制搜索树(BST)的根,将其转换为大树,以便原始BST的每个键都更改为原始键加上大于BST中原始键的所有键的总和。
提醒一下,二叉搜索树是满足以下约束的树:
节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左子树和右子树也必须是二叉搜索树。
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,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 bstToGst(self, root: TreeNode) -> TreeNode:
我对如何处理这个问题感到困惑。最初,我以为我会对提供的列表进行某种循环。但是,在阅读了讨论中的一些示例响应后,我看到使用了root.right和root.left等命令。我如何在Jupyter笔记本中执行此操作?我对TreeNodes没有经验,所以我想以正确的方式解决这个问题,并学习基本概念,而不是以另一种方式暴力破解它。非常感谢所有帮助。
谢谢
定义一个迭代器函数,以逆序遍历节点,然后累加反向遍历节点的总数,并将值分配给每个节点:
class Solution:
def revNodes(self,node):
if node.right: yield from self.revNodes(node.right)
yield node
if node.left: yield from self.revNodes(node.left)
def bstToGst(self, root):
total = 0
for node in self.revNodes(root):
node.val = total = node.val + total
输出:
data = [4,1,6,0,2,5,7,None,None,None,3,None,None,None,8]
nodes = [v if v is None else TreeNode(v) for v in data]
for i,node in enumerate(nodes):
if not node: continue
if 2*i+1<len(nodes): node.left = nodes[2*i+1]
if 2*i+2<len(nodes): node.right = nodes[2*i+2]
root = nodes[0]
print(root) # BEFORE
4
__/ \_
1 6
/ \ / \
0 2 5 7
\ \
3 8
Solution().bstToGst(root)
print([node.val if node else None for node in nodes])
[30, 36, 21, 36, 35, 26, 15, None, None, None, 33, None, None, None, 8]
print(root) # AFTER
30
__/ \__
36 21
/ \ / \
36 35 26 15
\ \
33 8
请注意,为了打印树,我必须向 TreeNode 类添加一个 repr() 方法
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __repr__(self):
nodeInfo = lambda n:(str(n.val),n.left,n.right)
return "\n".join(printBTree(self,nodeInfo,isTop=False))
printBTree函数来自我以前在这里提供的另一个答案
树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: 树有多个节点(node),用以储存元素。某些节点之间存在一定的关系,用连线表示,连线称为边(edge)。边的上端节点称为父节点,下端称为子节点。树像是一个不断分叉的树根。 每个节点可以有多个子节点(children),而该节点是相应子节点的父节点(parent)。比如说,3,5是6的子节点,6是3,
我很难按我教授想要的格式打印出一个二叉搜索树。 他的格式是这样的: 我的代码:
我说得对吗?
我写了一个函数,如果给定的二叉树是二叉搜索树,则返回true,否则返回false。 我的功能对吗?
在二元搜索树的情况下,为什么我们不能简单地在一个节点有两个子节点的情况下,将一个节点的前一个节点替换为后一个节点?
我必须编写一个二进制搜索树的实现,它可以处理库的库存。它读取一个包含所有书籍的文本文件,并将这些书籍按字母顺序添加到树中。我已经与Insertar()函数代码斗争了几天,但我无法使它正常工作,它基本上接收到一个指针,指向与书相关的所有数据的树根。如果根为NULL,则它将函数中输入的所有值初始化一个节点,并将内存方向指定为NULL节点。问题是,它在本地做,最终它没有分配它。谁能帮我纠正那个具体的功能