[트리] 리트코드(Leetcode)/2265 - Count Nodes Equal to Average of Subtree

 

 

 PROBLEM 

Count Nodes Equal to Average of Subtree - LeetCode

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};	// 현재 서브트리의 합과 카운트를 리턴 시켜줌
}