979. Distribute Coins in Binary Tree | 1709
Surprise second question from today cuz I feel like it.
I have to consult some hint to get the idea. I could only think of the idea of carrying over the balance/debt but I can’t think of the way to implement it.
1# Definition for a binary tree node.
2# class TreeNode:
3# def __init__(self, val=0, left=None, right=None):
4# self.val = val
5# self.left = left
6# self.right = right
7class Solution:
8 def distributeCoins(self, root: Optional[TreeNode]) -> int:
9 self.total_moves = 0
10
11 def dfs(node: Optional[TreeNode]) -> int:
12 if not node:
13 return 0
14 l = dfs(node.left)
15 r = dfs(node.right)
16
17 debt = l + r - node.val + 1
18 self.total_moves += abs(debt)
19 return debt
20
21 dfs(root)
22 return self.total_moves
#Tree #Depth-First-Search #Python