👀 문제
https://leetcode.com/problems/symmetric-tree/
👊 도전
1. 설계
- 큐에서 두 개를 뽑고, 두 값이 같다면 a의 왼쪽, b의 오른쪽, a의 오른쪽, b의 왼쪽을 순서대로 넣는다.
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
/**
*
* @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 boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q=new LinkedList<>();
q.offer(root);
q.offer(root);
while(!q.isEmpty()){
TreeNode a=q.poll();
TreeNode b=q.poll();
// 두 개 비교
if(a==null && b==null) continue;
if(a==null || b==null) return false;
if(a.val!=b.val) return false;
// 두 값이 대칭이라면 순서대로 넣기
q.offer(a.left);
q.offer(b.right);
q.offer(a.right);
q.offer(b.left);
}
return true;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 큐를 이용한다
- 큐에서 두 개씩 뽑아 값을 비교한다. 루트는 하나기 때문에 같은 값을 두 번 넣어준다.
- 큐에서 두 개를 뽑는다. a와 b가 둘 다 null이라면 자식 노드도 없으므로 바로 continue한다.
- 둘 중 하나가 null이면 대칭이 아니므로 false를 리턴한다.
- 값이 달라도 false이다.
- 값이 같다면 자식 노드들을 넣어준다. 비교하는 대상이 정해져있기 때문에 순서를 맞춰서 넣는다.
- a의 왼쪽은 b의 오른쪽과, a의 오른쪽은 b의 왼쪽과 비교해야 하므로 차례대로 넣는다.