推 JIWP: 別卷了，去玩活俠傳 06/26 00:54
→ sustainer123: 我97小時了 時間小偷 06/26 00:59
→ sustainer123: 然後我kaggle本來120 還想拼一下 06/26 00:59
→ sustainer123: 結果這幾天都在玩 直接170 我印象快截止了 GG 06/26 00:59
推 oin1104: 寶 我快哭了 安慰我 06/26 01:02
推 JIWP: 大師，別卷了，快去玩遊戲 06/26 01:02
※ 引述《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
感覺能寫得更漂亮 但我腦子一片混亂 晚安
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.249.64 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719334058.A.424.html