[leetcode][979] Distribute Coins in Binary Tree

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

---

루트에서 자식노드로 내려가면서 현재 탐색 중인 노드를 루트로 하는 서브트리의 모든 노드들이 코인을 하나씩 가지고 남는 코인개수를 반환한다. 이 함수를 getCoins라 한다면 수도코드는 다음과 같다.

getCoins(root) = getCoins(root.left) + getCoins(root.right) + root.val - 1

root 노드의 val(가지고 있는 코인 개수)와 자식 노드들에게서 남는 코인개수를 가져와서 더해준다.

그리고 1을 빼준다. 이유는 root 노드도 1개의 코인을 가져야하기 때문에 root 몫의 코인 개수(1개)는 제외시켜야 하기 때문이다.

 

남는 코인개수를 구했다면 개수의 절대 값을 전체 이동 횟수에 더해준다.

절대 값을 더하는 이유는 남는 코인개수가 음수가 될 수 있기 때문이다. 

음수가 되는 경우는 서브트리 노드들이 가지고 있는 코인 개수보다 노드의 개수가 더 많은 경우이다. 

이 경우 getCoins의 반환 값(x라 하자)은 음수가 되는데, 이 경우 다른 노드들에게서 코인을 가져올것이기 때문에 탐색 중인 노드의 부모 노드에게서 -x 개의 코인을 가져오게 되어있다. 즉, 부모노드 -> 탐색노드로 -x번의 코인 이동이 발생할 것이다.

x가 양수인 경우는 반대로 탐색노드 -> 부모노드로 x번의 코인 이동이 발생한다.

즉 양수, 음수인 경우 |x|번의 코인 이동이 부모노드와 탐색 노드 간 발생하는 건 변함이 없기 때문에 |x|를 전체 이동 횟수에 더해주어야 한다.

 

모든 노드를 탐색했을 때 전체 이동 횟수가 정답이 된다.

시간복잡도는 O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/979.%20Distribute%20Coins%20in%20Binary%20Tree.py