Leetcode Problem 1038.二叉搜索树到大和树 --> Python

Question

我在用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没有经验，所以我想以正确的方式解决这个问题，并学习基本概念，而不是以另一种方式暴力破解它。非常感谢所有帮助。

谢谢

Answer 1

定义一个迭代器函数，以逆序遍历节点，然后累加反向遍历节点的总数，并将值分配给每个节点:

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函数来自我以前在这里提供的另一个答案