Leetcode 979. Distribute Coins in Binary Tree

문제

You are given the root of a binary tree with n nodes where each node in the tree 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

이진트리의 루트가 주어지고 노드는 정수 값을 포함한다.
한 노드에서 한 노드로 값 1을 전달해줄수 있을때, 모든 노드가 1을 값으로 가지기 위해 필요한 전달 횟수를 구하시오.

예시

• 루트에서 한개씩 왼쪽 오른쪽으로 전달한다.
• 총 2회

• 3을 가진 노드에서 2만큼 루트로 전달 ( 2회 )
• 루트에서 오른쪽 노드로 1만큼 전달 ( 1회 )
• 2 + 1 총 3회

제한

• 트리엔 총 n개의 노드가 있다.
• $1 <= n <= 100$
• $0 <= Node.val <= n$
• 모든 노드의 값을 합치면 n이 된다.

풀이법

• 리프에서부터 위로 올라간다.
• 자신을 루트로 가지는 서브 트리가 여러개 생긴다.
• 여기서 서브트리의 사이즈와 서브트리에 포함된 총 노드의 합을 구할수 있다.
• 여기서 두가지로 경우가 나뉘는데,

1. 서브트리의 크기보다 코인의 수가 많은경우
   • 많은 코인만큼을 이동해야 한다.
2. 서브트리의 크기보다 코인의 수가 적은경우
   • 적은 코인만큼 가져와야 한다.

• 즉, 최소한 두 값의 차이만큼의 이동이 서브트리의 루트에서 필요하다.
• 이 연산을 서브트리의 루트가 될 모든 노드 ( 트리의 모든 노드 ) 에 대해 구해서 한데 더하면
• 총 이동 횟수가 나온다!

# 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.res = 0
        def dfs(cur):
        	# 없을 경우 사이즈 = 0, 코인 = 0
            if not cur:
                return [0, 0]
                
            # 왼쪽 서브트리와 오른쪽 서브트리 취합
            l_size, l_coin = dfs(cur.left)
            r_size, r_coin = dfs(cur.right)
			
            # 서브트리의 크기와 총 노드 합
            size = 1 + l_size + r_size
            coins = cur.val + l_coin + r_coin

			# 필요한 최소한의 이동을 구해 전역변수에 더한다.
            self.res += abs(size - coins)

			# 상위 루트를 위해 전달. ( 최종적으로는 사용되지 않음 )
            return [size, coins]

        dfs(root)

        return self.res