(강의내용 누락)이진트리 reconstract 로직 설명

관련 작성글 : 자료구조 - Data Structures with Python

강의 영상 (유튜브) : 자료구조 - 이진트리 - 정의와 순회(23:46~)

preorder와 inorder 결과물로 이진트리 유추하는 방법

• 깃허브에서 이슈 커멘트 확인

preorder: ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']
inorder: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']

1. Preorder 순회에서 루트 노드 찾기:
   • preorder의 첫 번째 요소는 루트 노드입니다. 여기서는 'F'가 루트 노드입니다.
2. Inorder 순회에서 루트 노드를 기준으로 좌우 나누기:
   • 'F'를 기준으로 inorder를 좌우로 나눕니다.
   • 왼쪽 서브트리의 inorder는 ['A', 'B', 'C', 'D', 'E'], 오른쪽 서브트리의 inorder는 ['G', 'H', 'I'] 입니다.
3. Preorder 순회에서 왼쪽 서브트리와 오른쪽 서브트리 찾기:
   • preorder에서 루트 다음에 나오는 요소들은 왼쪽 서브트리의 노드들입니다.
   • 왼쪽 서브트리의 preorder는 ['B', 'A', 'D', 'C', 'E'], 오른쪽 서브트리의 preorder는 ['G', 'I', 'H'] 입니다.
4. 재귀적으로 서브트리를 생성하기:
   • 왼쪽 서브트리의 루트는 왼쪽 서브트리의 preorder의 첫 번째 요소인 'B'이고, 그에 해당하는 inorder는 ['A', 'B', 'C', 'D', 'E']입니다.
   • 오른쪽 서브트리도 동일한 방식으로 생성합니다.
5. 반복:
   • 이 과정을 계속 반복하여 트리를 완성합니다.

  #        F
  #      /   \
  #    B      G
  #   / \      \
  #  A   D      I
  #     / \    /
  #    C   E  H