👀 문제
https://leetcode.com/problems/symmetric-tree/
👊 도전
1. 설계
- 큐를 이용해 트리를 순회한다.
- 현재 큐에 남아있는 값들이 같은 레벨인 것이므로 현재 큐의 개수만큼 뽑아서 리스트에 저장한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
*
* @author HEESOO
*
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result=new ArrayList<>();
Queue<TreeNode> q=new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int size=q.size(); // 현재 노드 개수==현재 레벨의 노드 개수
ArrayList<Integer> list=new ArrayList<>();
for(int i=0;i<size;i++){
TreeNode node=q.poll();
if(node==null) continue;
list.add(node.val);
q.offer(node.left);
q.offer(node.right);
}
if(list.size()!=0) result.add(list);
}
return result;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 큐를 이용한다
- 큐를 이용해 트리를 방문한다.
- 현재 큐에 있는 노드들은 같은 레벨인 것과 같다.
- 하지만 while문 처음에 poll한 node의 left와 right를 또다시 큐에 넣으면 큐의 사이즈가 바뀌기 때문에, 큐의 사이즈를 size에 저장해놓고, 그 개수만큼 for문을 돌려 노드를 뽑는다.
- 뽑은 노드가 null이 아니라면, list에 넣는다.
- size만큼 뽑아서 list에 저장한 것이 하나 이상 존재하면 result에 넣는다. 해당 코드가 없으면 빈 리스트가 result에 들어간다.