Hackerrank - BST Level-Order Traversal

https://www.hackerrank.com/challenges/30-binary-trees/problem

Day 23: BST Level-Order Traversal | HackerRank

오늘 푼 문제는 그저께 생성하는 법을 배운 Binary Search Tree를 level 별로 출력하는 것입니다.

아래와 같은 그림이 주어지면, Level 0, Level 1, Level 2 순서로 node의 값들을 나열하면 됩니다.

즉, 아래의 Example에서는 3 2 5 1 4 7 의 순서대로 값을 출력하면 됩니다.

이번 문제는 회귀로 풀 수 없을 것 같아서 다른 방법을 적용했습니다.

(별로 안 좋은 방법 같아서 참고만 해주세요..ㅎ)

 

* 변수 : 

1) current_height : 출력할 Level에 있는 Node들을 담은 배열입니다.

2) next_height : 다음에 출력할 Level에 있는 Node들을 담은 배열입니다.

 

* 방법 : 

 

0. 초기화 : 

current_height = [root], next_height = []

while(current_height):

1. 입력받은 노드의 값을 출력한다.

2. 입력받은 노드의 왼쪽 / 오른쪽 Subtree 존재 여부를 확인한 뒤, next_height에 추가한다.

3. current_height = next_height으로 치환한다.

4. next_height = []으로 초기화한다.

 

이렇게 되면, current_height에 원소가 존재할 때까지 계속 출력을 하게 됩니다.

current_height은 next_height, 즉 current_height의 subtree들로 계속 업데이트가 되므로, 마지막 Level까지 출력을 계속하게 됩니다.

 

이 방법에서 문제가 될만한 소지는, while문의 조건을 계속 치환하여 변환한다는 점입니다.

뭔가 찜찜한 느낌이 계속 들지만....일단 돌아가니 문제를 푼 것 같습니다.

이상 끝-!