[LeetCode] 979. Distribute Coins in Binary Tree

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

leetcode - Distribute Coins in Binary Tree

문제 유형 : 이진트리, dfs, 재귀, 부분합

문제 난이도 : Medium

 

 

문제

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.

 

당신은 이진트리의 root를 받는다. n개의 노드가 있고, 각 노드는 node.val개의 코인이 있다.

n개의 코인이 있다.

 

한 개의 이동에서, 우리는 두 인접한 노드를 골라 한 코인을 이동시킬 수 있다.

모든 노드가 한 개의 코인을 갖는 최소 이동 수를 구하시오.

 

풀이

우선, 현재 서브트리의 루트가 null이면 0을 반환한다.

양쪽 자식들의 서브트리의 이동 수를 재귀호출하여 구한다.

현재 노드값에서 1을 빼서 필요한, 또는 넘치는 코인수를 구한다.

이를 부모노드의 val에 더한다.

 

양쪽 자식들의 서브트리의 이동 수 + 필요한 또는 넘치는 코인수의 절대값을 반환한다.

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * };
 */

class Solution {
public:
    int distributeCoins(TreeNode* root, TreeNode* parent = NULL) {
        if(!root) return 0;
        int m = distributeCoins(root -> left, root) + distributeCoins(root -> right, root);
        int x = root -> val - 1;
        if(parent) parent -> val += x;
        m += abs(x);

        return m;
    }
};