※ 引述《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
感覺能寫得更漂亮 但我腦子一片混亂 晚安