aboutsummaryrefslogtreecommitdiff
path: root/distribute_coins_binary_tree.py
diff options
context:
space:
mode:
authorjack <0x6A73@pm.me>2024-06-14 13:13:15 -0600
committerjack <0x6A73@pm.me>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /distribute_coins_binary_tree.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'distribute_coins_binary_tree.py')
-rw-r--r--distribute_coins_binary_tree.py35
1 files changed, 35 insertions, 0 deletions
diff --git a/distribute_coins_binary_tree.py b/distribute_coins_binary_tree.py
new file mode 100644
index 0000000..e14f7a4
--- /dev/null
+++ b/distribute_coins_binary_tree.py
@@ -0,0 +1,35 @@
+# 979. Distribute Coins in Binay Tree
+
+"""
+given the 'root' of a binary tree with 'n' nodes where each 'node' is the
+tree that has 'node.val' coins. there are 'n' coins in total throughout the
+whole tree. in one move, we may choose two adjacent nodes and move one coin
+from one node to another. a move may be from parent to child, or from child
+to parent. return the minimum number of moves required to make every node
+have exactly one coin.
+"""
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+ def __init__(self, val=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+
+class Solution(object):
+ def distributeCoins(self, root):
+ """
+ :type root: TreeNode
+ :rtype: int
+ """
+
+ def dfs(node):
+ if not node:
+ return 0, 0
+ (lbal, lcnt), (rbal, rcnt) = dfs(node.left), dfs(node.right)
+ bal = node.val + lbal + rbal - 1
+ return bal, lcnt + rcnt + abs(bal)
+
+ return dfs(root)[1]