Try   HackMD

979. Distribute Coins in Binary Tree

Difficulty: Medium

link: https://leetcode.com/problems/distribute-coins-in-binary-tree/

1. DFS

O(N)
runtime,
O(H)
space

定義dfs函數,計算以node為root的subtree,扣掉每個child node需要的1枚硬幣後,總共會多(或少)幾枚硬幣。

如果硬幣有多,回傳值就是正的;如果硬幣有缺,回傳值就是負的;剛剛好不多不缺的情況,回傳值為0。

dfs函數顯示,node最少還需要幾枚硬幣(缺硬幣的情況),或著node至少要給出幾枚硬幣(多硬幣的情況),才能達成題目要求的硬幣分布。

假設parent node會滿足node的這個最低需求,通過計算parent node <-> node的硬幣流量,就能得知最少的移動步數。

python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def distributeCoins(self, root: Optional[TreeNode]) -> int: self.moves = 0 def dfs(node): if node is None: return 0 coins = dfs(node.left) + dfs(node.right) + node.val - 1 self.moves += abs(coins) return coins dfs(root) return self.moves

官方解答。

前一個方法是計算自己到parent node的硬幣流量,這個方法是計算小孩到自己的硬幣流量,考慮到邊界case:dfs(root)和dfs(None)都為0,兩個方法等效。

python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def distributeCoins(self, root: Optional[TreeNode]) -> int: self.ans = 0 def dfs(node): if not node: return 0 L, R = dfs(node.left), dfs(node.right) self.ans += abs(L) + abs(R) return node.val + L + R - 1 dfs(root) return self.ans
tags: leetcode