※ 引述《DJYOMIYAHINA (通通打死)》之铭言：
: 马的
: 不知道为啥觉得整个阴阳怪气
: 超卡
: 可能太晚了==
: 晚安
: def bstToGst(self, root: TreeNode) -> TreeNode:
: def dfs(root: TreeNode, summ) -> int:
: if root is None:
: return summ
: right = dfs(root.right, summ)
: root.val += right
: left = dfs(root.left, root.val)
: return left
: dfs(root, 0)
: return root
思路:
先加右子树 之后左子树
这样就能完成要求又维持二元搜寻树
Python Code:
# 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:
def dfs(node):
nonlocal sum
if not node:
return
dfs(node.right)
tmp = sum
sum += node.val
node.val += tmp
dfs(node.left)
sum = 0
dfs(root)
return root
感觉能写得更漂亮 但我脑子一片混乱 晚安