트리. [1991]

[1. 문제 설명]

이진 트리를 입력 받아

전위 순회, 중위 순회, 후위 순회 결과를 출력하도록 한다.

(tree 에서 node 의 값은 알파벳이며, child 가 없는 경우 '.' 으로 표시한다.)

 

 

 

[2. 풀이 접근]

A. 재귀로 푸는 방법

전위 순회(inorder traverse) 를 예로 들면,

                                 root

         left_sub_tree             right_sub_tree

 

root 를 먼저 방문하고,

왼쪽 sub tree 를 그 다음으로 방문하며,

오른쪽 sub tree 를 가장 마지막에 방문한다.

 

여기서, left_sub_tree, right_sub_tree 에 대해서 동일하게 각 sub tree 에 root 를 먼저 방문해야 하는데,

이는 전체 문제의 부분 문제로 다룰 수 있다.

 

따라서 재귀적으로 접근 할 수 있다.

 

 

B. 스택을 이용하여 푸는 방법

=> 연결 된 링크 참조

 

 

[3. 코드]