문제
- 아래 그림과 같은 이진트리를 레벨탐색 연습하세요.
입력
- 생략
출력
- 레벨 탐색 순회 출력 : 1 2 3 4 5 6 7
입출력 예제
- 생략
풀이방식
이번 문제는 이진트리, 큐, 재귀함수를(을) 사용하여 푸는 문제이다.
더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)
설계과정
1. 큐에 노드들을 저장한다.
2. 트리에 레벨을 설정하여 각 레벨에 해당하는 노드들을 확인한다.
3. 해당 레벨에 해당하는 모든 노드들을 큐에서 꺼내고 출력한다.
풀이과정
1. NodeTwo 클래스를 생성하고, 각 변수들을 선언 및 초기화한다.
- data : 각 트리의 값이 들어갈 변수이다.
- lt, rt : 각각 왼쪽과 오른쪽 노드의 값을 저장할 변수이다.
- ch[ ] : 부분집합의 사용여부 값을 저장할 배열이다.
2. BFS 메소드를 작성한다.
- BFS란 너비 우선 탐색으로 루트 혹은 임의의 다른 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다.
3. Q를 선언하고 root를 저장한다.
- 메인에서 선언하는 값을 Q에 저장한다는 의미이다.
4. 레벨을 저장하는 변수를 선언한다.
5. Q가 비어있지 않으면 계속해서 도는 while 문을 선언한다.
6. Q의 크기를 저장하는 변수 len을 선언한다.
- len은 Q의 크기 즉, 각 레벨에 해당하는 노드의 개수를 의미한다.
7. for문을 통해 루트 노드와 그 자식 노드들의 값을 출력한다.
- 1회차 for문에서 cur.data 의 값은 루트 노드의 값으로, 1을 의미한다.
8. for 문이 끝나면 L을 증가시켜 다음 레벨을 탐색하고 동일하게 레벨에 맞는 노드들을 출력한다.
해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
