[2024] day 140. Leetcode 979. Distribute Coins in Binary Tree

gunny·2024년 5월 18일

Leetcode 979. Distribute Coins in Binary Tree Leetcode 979. Distribute Coins in Binary Tree python

코딩테스트

목록 보기

454/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 18일 (토)
Leetcode daily problem

979. Distribute Coins in Binary Tree

https://leetcode.com/problems/distribute-coins-in-binary-tree/?envType=daily-question&envId=2024-05-18

Problem

트리의 각 노드에 코인이 있는 n개의 노드로 이루어진 이진 트리의 루트가 제공된다. 전체 트리에는 총 n개의 코인이 있다.

한 번의 이동으로 두 개의 인접한 노드를 선택하고 하나의 동전을 한 노드에서 다른 노드로 이동시킬 수 있다. 이동은 부모에서 자식으로, 또는 자식에서 부모로 이루어질 수 있다.

모든 노드가 정확히 하나의 코인을 갖도록 만드는 데 필요한 최소 이동 횟수를 반환한다.

Solution

dfs

코드는 이진 트리의 모든 노드를 한 번씩 방문하는 깊이 우선 탐색(DFS)을 수행한다.
트리의 각 노드는 정확히 한 번씩 방문되고, 방문 시에 상수 시간 작업(노드의 값 확인, 자식 노드로 이동, 코인 이동 횟수 갱신)을 수행한다.

각 노드에 대해, 왼쪽과 오른쪽 서브트리의 남는 코인 또는 부족한 코인의 수를 계산한다.
현재 노드에서 필요한 코인 이동 횟수를 abs(left_coins) + abs(right_coins)로 누적한다.
현재 노드의 최종 상태를 계산하여 부모 노드로 반환합니다. 즉, 현재 노드의 코인 수 - 1 (자기 자신을 위해 필요한 코인 1개) + left_coins + right_coins를 반환한다.

Code

class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        self.moves = 0

        def dfs(node):
            if not node:
                return 0
            
            left_coins = dfs(node.left)
            right_coins = dfs(node.right)

            self.moves += abs(left_coins) + abs(right_coins)

            return (node.val-1) + left_coins + right_coins
        
        dfs(root)
            
        return self.moves