PreOrder + InOrder or PostOrder + InOrder로 Binary Tree 만들기

1. 동일한 Tree의 PreOrder, InOrder traverse의 결과가 담겨진 배열 2개가 주어질 때 Binary Tree를 만드는 문제이다.

 

2. 기본적으로 두개의 다른 Traverse 결과가 있으면 바이너리 트리를 만드는 알고리즘은 혼자서 찾기힘들기 때문에 기본적으로 인지하고 있는 것이 중요하다. -> 기본지식 (모르면 인터뷰에서 풀 수 없다.)

 

3. 문제는 잘 알려진 이 알고리즘을 어떻게 구현할지인데 상당히 까다롭다.

 

4. 재귀를 사용하여 문제를 풀 때는 Top down과 Botton up 둘 중 하는 사용하는데 일반적으로는 Botton up이 훨씬 직관적이고 많이 사용된다.

 

5. 이 문제는 Top down 방식을 사용하여 문제를 해결해야 편리하다. 익숙하지 않기 때문에 어려운 것이다.

  5-1 배열이 끝나면 재귀가 끝나게 되는데 배열이 끝나면 작업도 끝나는 구조이다. 그래서 배열을 소모하는 문제는 Top Down이 편리하다.

  5-2 루트를 만드는 것과 자식노드를 만드는 구조가 동일하다. 따라서 재귀가 당연히 사용되고 구조도 간단하다. 이 문제는 얼마나 Top down으로 재귀처리하는 것에 익숙한가이다.

  5-3 순차적으로 preorder는 검색을 수행할 것이고 preorder와 inorder에서 일치하는 그 값이 현재의 root가 되므로 새로운 노드를 만들고 이 노드를 반환하면 된다. 이 반환값은 부모의 좌나 우측 자식이 된다.

  5-4 선택된 inorder값 기준으로 좌우로 구분해서 재귀를 호출하고 결과를 좌우 자식노드에 대입하면 된다.