[Tree] 백준 : 9934_완전 이진 트리

[inseonyun]

Source URL : 백준 : 9934_완전 이진 트리

문제 요구사항 :

• 첫째 줄에 K (1 ≤ K ≤ 10)가 주어진다.
• 둘째 줄에는 상근이가 방문한 빌딩의 번호가 들어간 순서대로 주어진다.
• 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2K)에 포함된다.
• 총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다.
• 출력은 왼쪽에서부터 오른쪽 순서대로 출력한다.

접근 방법 :

• 완전 이진 트리의 노드 개수는 2^Depth( 문제에선 K ) -1이다. 즉, K가 3이라면 노드 개수는 7개가 된다.
• 그렇담 문제에서 주어진 노드들을 배열에 담아 가운데 인덱스부터 접근해 재귀로 인덱스를 2로 나누며 접근하면, 왼쪽, 오른쪽 노드를 차례로 방문해 완전 이진 트리를 나타내는 벡터 answer를 만들 수 있다.

풀이 순서 :

1. K를 입력 받아 pow 함수를 이용해 Node의 개수를 구한다
2. Node의 개수만큼 for문을 반복해 노드 정보를 배열에 저장한다.
3. 트리의 최상단 루트를 기준으로 탐색하며, vector에 순서대로 담아준다.
4. 루트 노드 idx는 start_idx와 end_idx를 더하고 2로 나눈 값이 된다. answer의 depth 인덱스에 tree[ 루트 노드 idx ] 값을 넣는다.
5. 이후 반복해서 왼쪽 노드 탐색, 오른쪽 노드 탐색을 이어간다.

[inseonyun]

문제 풀이 결과 :