[Leetcode/C#] 637. Average of Levels in Binary Tree

 

문제링크 

https://leetcode.com/problems/average-of-levels-in-binary-tree/?envType=study-plan-v2&envId=top-interview-150

 

637. Average of Levels in Binary Tree

 

 

기억하면 좋을 것 

 

public class Solution {
    Queue<TreeNode> queue = new Queue<TreeNode>();
    List<double> result = new List<double>();
    int sumInSameLevel = 0;
    int cntInSameLevel = 0;
   
    public IList<double> AverageOfLevels(TreeNode root) {
        queue.Enqueue(root);
        traverse();
        return result;
    }
     private void  traverse()
    {
        while(queue.Count > 0)
        {
            cntInSameLevel = queue.Count;
            for(int i = 0; i<cntInSameLevel; i++)
            {
                TreeNode tmpnode = queue.Dequeue();
                sumInSameLevel += tmpnode.val;
                if(tmpnode.left != null) queue.Enqueue(tmpnode.left);
                if(tmpnode.right != null) queue.Enqueue(tmpnode.right);
            }
            result.Add((double)sumInSameLevel / (double)cntInSameLevel);
            sumInSameLevel = 0;
            cntInSameLevel = 0;
        }
    }
}

 

 이렇게 풀어줬는데 

[2147483647,2147483647,2147483647] 이 테스트케이스에서 

[2147483647.00000,-1.00000] 이 답이 나와 Wrong 이라고해서 왜 그런지가 궁금했다. 

왜 뜬금없이 -1?

이유는 내가 node 들 값을 더하기 위해 생성해준 sumInSameLevel 이 int 타입이기때문에 

2147483647 + 2147483647 을 해주면서 int 가 담을 수 있는 최대 크기인 2147483647 을 넘어가버려 잘못된 값이 들어간거였다. 그래서 sumInSameLevel 을 long 타입으로 바꿔줬다. 

long 은 C#에서 64비트 정수

int 는 C#에서 32비트 정수다

 

소감

bfs를 너무 오랫만에 풀어서 bfs = queue 사용, 방문처리 필요시 방문처리 배열 생성 필요 

이 조건을 완전히 잊고있었다.. 

bfs 에서 계층별 구분이 필요한 문제라면 while 안에 for 문을 넣고 그 안에서 queue.count 만큼 반복을 돌려 

node 를 빼내면서 계산해주면 된다. 

역시 개념이 가장 중요한 것 같다. 

 

해결 코드

public class Solution {
    Queue<TreeNode> queue = new Queue<TreeNode>();
    List<double> result = new List<double>();
    long sumInSameLevel = 0;
    int cntInSameLevel = 0;
   
    public IList<double> AverageOfLevels(TreeNode root) {
        queue.Enqueue(root);
        traverse();
        return result;
    }
     private void  traverse()
    {
        while(queue.Count > 0)
        {
            cntInSameLevel = queue.Count;
            for(int i = 0; i<cntInSameLevel; i++)
            {
                TreeNode tmpnode = queue.Dequeue();
                sumInSameLevel += tmpnode.val;
                if(tmpnode.left != null) queue.Enqueue(tmpnode.left);
                if(tmpnode.right != null) queue.Enqueue(tmpnode.right);
            }
            result.Add((double)sumInSameLevel / (double)cntInSameLevel);
            sumInSameLevel = 0;
            cntInSameLevel = 0;
        }
    }
}

 

 

 

Submission Detail