728x90
반응형
https://github.com/ROUTINE-STUDY/Algorithm
ROUTINE-STUDY/Algorithm
초보 알고리즘 스터디 / 누구나 참여 가능 :runner:. Contribute to ROUTINE-STUDY/Algorithm development by creating an account on GitHub.
github.com
알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
문의는 댓글 혹은 GitHub 주소를 참고해주세요.
문제 출처 : https://leetcode.com/problems/average-of-levels-in-binary-tree/
Average of Levels in Binary Tree - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제 설명
주어진 TREE의 각 depth별 평균 값을 담은 배열(리스트)를 반환하세요
풀이방법
기본 BFS 탐색 로직을 그대로 사용하였습니다.
1. Depth별 평균 값을 구해야하기 때문에, Depth 당 값을 합산하는 sum 변수를 0으로 초기화
2. sum과 depth별 노드의 개수(size)를 나누어 평균 값을 계산
자바에서 double형과 int형을 연산하면 double형이 return 되기 때문에 불필요한 형 변환을 하지 않도록 코딩했습니다.
내 코드(JAVA)
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
double sum = 0; // depth별 합산 초기화
for(int i=0; i<size; i++) {
TreeNode node = q.poll();
if(node.left != null) q.add(node.left);
if(node.right != null) q.add(node.right);
sum += node.val; // 값 누적
}
res.add(sum/size); // 평균 값 계산 후 추가
}
return res;
}
728x90
반응형
'알고리즘' 카테고리의 다른 글
[LeetCode/JAVA] 58. Length of Last Word (0) | 2021.07.18 |
---|---|
[LeetCode/JAVA] 66. Plus One (0) | 2021.07.18 |
[LeetCode/JAVA] 14. Longest Common Prefix (0) | 2021.07.17 |
[LeetCode/JAVA] 500. Keyboard Row (0) | 2021.07.17 |
[LeetCode/JAVA] 389. Find the Difference (0) | 2021.07.17 |
댓글