👀 문제
https://leetcode.com/problems/maximum-depth-of-binary-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
/**
*
* @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 int maxDepth(TreeNode root) {
int depth=-1;
Queue<TreeNode> q=new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int size=q.size();
depth++; // 현재 레벨 계산
for(int i=0;i<size;i++){ // 레벨에 있는 노드 체크
TreeNode node=q.poll();
if(node==null) continue;
q.offer(node.left);
q.offer(node.right);
}
}
return depth;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 큐를 이용한다
- 레벨순회를 통해 레벨 개수를 셌다.
- 큐의 사이즈를 체크해서 size에 저장한다. 현재 레벨에 size만큼 노드가 있다는 뜻이다. 이 개수만큼 for문을 돌며 자식 노드들을 큐에 다시 넣는다. for문에서 size대신 q.size()를 쓰면, 밑에서 큐에 값을 삽입하며 큐 size가 계속 갱신되기 때문에 안된다.
- depth는 -1로 초기화한다. root가 들어오면 depth++하여 0이 되도록 하기 위함이다.