推 SecondRun: 別捲了 05/19 21:57
推 devilkool: 我不看解答根本想不到這個思維 05/19 21:58
→ DJYOSHITAKA: 今天怎麼是個hard:( 05/19 22:01
推 ray90514: Hard直接開擺 不過看答案好像差一點就想出來了 05/19 22:11
補一下昨天的:(
Distribute Coins in Binary Tree
其實還蠻不好想的
想了一陣子才想說可以往上回傳
"我要往上送多少金幣or我需要從上面收下多少金幣"
然後dfs的過程中 把往上送的跟從上面收下的都全部加起來就是答案了
有趣的一題
(如果沒想出來就是糞肏的一題了)
def __init__(self):
self.ans = 0
def dfs(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
left = self.dfs(root.left)
right = self.dfs(root.right)
self.ans = self.ans + abs(left) + abs(right)
return root.val + (left+right) - 1
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.dfs(root)
return self.ans
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.227.99 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716127001.A.3CF.html