Average of Levels in Binary Tree - LeetCode
Can you solve this real interview question? Average of Levels in Binary Tree - Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted. Examp
leetcode.com
이진 트리의 루트가 주어졌을 때, 각 레벨에 있는 노드의 평균값을 배열의 형태로 반환합니다.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].
Example 2:
Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]
문제접근
트리를 탐색하면서 노드의 평균값을 구해야 합니다.
DFS와 BFS를 활용할 수 있습니다.
이번에는BFS를 활용해서 탐색해 보겠습니다.
결과를 보면 왼쪽의 값부터 탐색을 하는것을 알 수 있습니다.
따라서 left부터 q에 넣어줄 것입니다.
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if(root==null){
return res;
}
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
double sum = 0;
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;
}
시간복잡도
트리를 전부 탐색하고 있습니다.
O(n)의 시간복잡도기 필요합니다.
다른사람의 풀이
DFS로 해결한 방벙입니다.
개인적으로 BFS보다 이해하기 어려운것 같습니다.
하지만 트리를 전부 탐색한다는 관점에서 이해하려고 하면 금방 이해될것입니다.
class Solution {
List<double[]> store = new ArrayList<>(); // it will store sum, no. of nodes at each level
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
traverse(root, 0);
for(double[] cur: store){
res.add(cur[0]/cur[1]);
}
return res;
}
private void traverse(TreeNode node, int level){
if(node == null) return;
if(store.size() <= level) store.add(new double[2]);
// update sum and no. of nodes at curlevel
store.get(level)[0] += node.val;
store.get(level)[1]++;
traverse(node.left, level+1);
traverse(node.right, level+1);
}
}
느낀점
트리 문제는 보통 트리를 탐색하는것에서 벗어나지 않는것 같습니다.
DFS, BFS를 둘다 잘 활용해서 푸는 연습을 해야겠습니다.
참고
JAVA || BOTH DFS & BFS SOLUTION WITH TC & SC - Average of Levels in Binary Tree - LeetCode
View jitendrap1702's solution of Average of Levels in Binary Tree on LeetCode, the world's largest programming community.
leetcode.com
'LeetCode' 카테고리의 다른 글
[LeetCode] 208. Implement Trie (Prefix Tree) (0) | 2023.09.10 |
---|---|
[LeetCode] 199. Binary Tree Right Side View (0) | 2023.09.07 |
[LeetCode] 230. Kth Smallest Element in a BST (0) | 2023.09.06 |
[LeetCode] 530. Minimum Absolute Difference in BST (0) | 2023.09.06 |
[LeetCode] 153. Find Minimum in Rotated Sorted Array (0) | 2023.09.05 |