PROBLEM
N = 서브트리의 합의 평균과 그 서브트리의 루트값과 같을 때를 카운트한 값
RETRY FLAG
Y
- 재귀에 대한 이해 다시 적립 필요
- 멍한 상태로 디버깅 하지말기
MY SOLUTION
아래는 전역변수로 관리하는 방식이고
마지막에 값이 들어가게 되는 최상단 루트인 4에서 node==null로 들어간 상태로 값을 돌려받는거라서
제대로 된 재귀호출을 할 수가 없다..
더보기
틀린 코드
class Main {
static int leftSubNodeSum;
static int leftSubNodeCount;
static int rightSubNodeSum;
static int rightSubNodeCount;
public static void main(String[] args) {
// ..
}
private static int traversal(TreeNode node, String direct) {
if (node == null) {
leftSubNodeSum = leftSubNodeCount = rightSubNodeSum = rightSubNodeCount = 0;
return 0;
}
if (node.left == null && node.right == null) {
if (direct.equals("left")) {
leftSubNodeSum += node.val;
leftSubNodeCount ++;
} else {
rightSubNodeSum += node.val;
rightSubNodeCount ++;
}
return 0;
}
int result = 0;
result += traversal(node.left, "left");
result += traversal(node.right, "right");
int totalCurrentSum = leftSubNodeSum + rightSubNodeSum + node.val; // 루트 포함해야돼서 루트값 더해줌
int totalCurrentCount = leftSubNodeCount + rightSubNodeCount + 1; // 루트 포함해야돼서 1 더해줌
if (totalCurrentSum / totalCurrentCount == node.val) {
answer ++;
}
return result;
}
}
REFERENCE SOLUTION
위의 방법으로 해결하기 위해서 계속 시도 했으나 답이 안나와서 다른 사람 풀이를 참고했다.
값을 돌려받기 위해서는 void가 아닌
count와 sum을 묶어서 하나의 배열(또는 객체로)을 리턴해주는 방식으로 처리해야 한다.
멀리서 보면 당연히 이렇게 해야하는건데 혼자할 때는 잘 떠오르지 않는 것을 보니 아직 연습이 많이 필요하다.
private static int[] traversal(TreeNode node) {
if (node == null) {
return new int[]{0, 0};
}
int[] left = traversal(node.left);
int[] right = traversal(node.right);
int currentSubSum = left[0] + right[0] + node.val; // 루트 포함해야돼서 루트값 더해줌
int currentSubCount = left[1] + right[1] + 1; // 루트 포함해야돼서 1 더해줌
if (currentSubSum / currentSubCount == node.val) {
answer ++;
}
return new int[]{currentSubSum, currentSubCount}; // 현재 서브트리의 합과 카운트를 리턴 시켜줌
}
'알고리즘 > 그래프' 카테고리의 다른 글
[트리] 리트코드(Leetcode)/1584 - Min Cost to Connect All Points (0) | 2022.08.09 |
---|---|
[BFS] 프로그래머스/1844 - 게임 맵 최단거리 (0) | 2022.06.09 |