.leetcode(979. Distribute Coins in Binary Tree)

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

 

1. 2022.02.20 시도

소요시간: 76분(36분 구상, 40분 풀이)

class Solution {
    public int distributeCoins(TreeNode root) {
        return traverse(root);
    }

    private int traverse(TreeNode root) {
        int left = 0;
        int leftv = 0;
        if (root.left != null) {
            left = traverse(root.left);
            leftv = root.left.val;
        }
        int right = 0;
        int rightv = 0;
        if (root.right != null) {
            right = traverse(root.right);
            rightv = root.right.val;
        }
        root.val = (root.val - 1) + leftv + rightv;
        return Math.abs(leftv) + Math.abs(rightv) + left + right;
    }
}

풀이 접근 과정

일단 거리와 코인을 구분해야겠다는 생각을 했다.

거리는 리턴값으로 넘겨주고 코인 갯수는 노드의 val로 표현하였다.

 

느낀점

• 코인과 거리를 구분하는 작업을 개념적으로는 간단했는데 코드로 풀자 꼬이기 시작했다. 특히 아래가 0인 노드인 경우, 보통 코인과 거리가 비슷하기때문에 엄청 헷갈린다.
• 나의 원리는 노드를 간단하게 하는데 있다. 노드에 저장되는 수는 실제 노드 수와 관계없고 앞으로 움직임을 계산하는데 쓰인다.
• 글로 설명해보려니 좀 어렵긴한데 말로 설명하는 것까지는 가능하다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형