補一下昨天的:(
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