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