python - Leetcode 问题 1038. 二叉搜索树到大和树 --> Python
问题描述
我在 Python 中做上面的 leetcode 问题。通常我所做的是在 jupyter notebook 中解决问题,然后在完成后将其复制并粘贴到 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 函数来自我过去在这里提供的另一个答案
推荐阅读
- r - 给定 R 中的其他标准,如何对特定列中的特定值求和?
- javascript - 无法在反应中使用道具设置状态
- javascript - Aframe 通过单击图标切换相机视图
- amazon-cognito - AWS AppSync - 致命错误:未设置凭证提供程序和终端节点
- flutter - 参数类型“项目”不能分配给参数类型“列表”
' - wordpress - 如何删除 Vimeo Embedded Player 上的下载按钮?
- html - 来自嵌套数组的 V-for
- plot - 绘图网络 - 节点太靠近
- pip - Pip extras 依赖替换
- python - 使用 django-hosts 时使用的正确命名空间是什么