Hackerrank Day 23 BST Level-Order Traversal

알고리즘 연습 사이트

www.hackerrank.com

Day 23:BST Level-Order Traversal

트리를 접근하는 순서에는 여러가지가 있다.


 1. InOrder Traversal
 일반적인 순서대로 트리의 노드를 접근한다. 
left-root-right 순서이다.

 2. PostOrder Traversal
 Post라는 말에서 유추할 수 있듯이 root 노드를 마지막에 두는 순서를 말한다. left-right-root 순서이다.

 3. PreOrder Traversal(DFS)
 PreOrder는 root노드를 가장 먼저 접근한다. 
root-left-right.  Depth-first-search라고도 한다.

 4. Level-Order Traversal(BFS)
 트리의 레벨 순서대로 검색한다. breath-first-search라고도 한다.

예시를 보면 위 4가지 방법을 어떤 순서로 진행되는지 이해하기 쉽다. 
아래 링크에서 이미지를 가져왔다.

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

hackerrank-Binary Tree

• InOrder: 1 2 3 4 5 6 7
• PostOrder: 1 3 2 5 7 6 4
• PreOrder: 4 2 1 3 6 5 7
• Level-Order: 4 2 6 1 3 5 7

이번 문제는 Binary search tree에서 Level-Order Traversal 방식대로 데이터를 꺼내와서 출력해야 한다.
이 문제를 해결하기 위해 Queue를 이용하면 매우 쉽게 문제가 해결된다. 
Day 18:Queues and Stacks 글 참조


 대표적인 Queue를 구현하는 클래스인 LinkedList 객체를 생성하고, 이 list에 2진탐색트리인 root 노드를 add한다.
 poll 메소드를 사용하였는데 poll은 리스트에 저장된 요소를 가져오면서 그 요소를 list 내에서 삭제해 준다. 
그리고 tmpNode에 현재 꺼내온 노드의 참조 주소를 저장하여 현재 노드의 left, right 자식이 존재하는지 체크하고 존재한다면 list에 add한다.  
add 할 때 주의점은 왼쪽에서 오른쪽 순으로 출력될 수 있도록 왼쪽부터 넣어야한다. 
 list가 비어있지 않는 동안은 계속 while문이 돌면서 data 값을 출력하게 된다.
 while문의 마지막에서 peek 메소드를 써 봤는데, 그다음 list에 요소가 존재할 때에만 data 간에 띄어쓰기를 넣어서 표출하기 위해서이다. 
 peek은 poll과 다르게 요소를 삭제 하지 않으므로 자식이 있다면 다음 반복을 탈 수 있게 된다.

static void levelOrder(Node root){
      LinkedList<Node> list = new LinkedList<Node>();

      list.add(root);
      while(!list.isEmpty()){
          Node tmpNode = list.poll();
          System.out.print(tmpNode.data);
          
          if(tmpNode.left != null){
              list.add(tmpNode.left);
          }
          if(tmpNode.right != null){
              list.add(tmpNode.right);
          }
          if(list.peek() != null)
            System.out.print(" ");
      }
}