이진트리

1단계: 기본 개념 이해하기

이진트리의 기본 구조

• 각 노드는 최대 2개의 자식 (left, right) 을 가짐
• 루트 노드부터 시작해서 계층적 구조
• 리프 노드는 자식이 없는 노드

 

기본 용어

• 높이(height): 루트에서 가장 깊은 노드까지의 거리
• 깊이(depth): 루트에서 특정 노드까지의 거리
• 완전 이진트리, 포화 이진트리 등의 특수한 형태

 

2단계: 기본 순회 방법 마스터하기

이진트리 문제의 90%는 순회가 핵심

• 전위 순회(Preorder): 루트 -> 왼쪽 -> 오른쪽
• 중위 순회(Inorder): 왼쪽 -> 루트 -> 오른쪽
• 후위 순회(Postorder): 왼쪽 -> 오른쪽 -> 루트
• 레벨 순회(Level-order): BFS 방식으로 레벨별로 순회
• 각 순회를 재귀와 반복문 두 가지 방식으로 모두 구현할 수 있어야 함

3단계: 문제 유형별 패턴 익히기

• 깊이/높이 관련 문제
  • 최대 깊이 구하기
  • 균형 트리 판별하기
  • 지름 구하기
• 경로 관련 문제
  • 루트에서 리프까지의 모든 경로
  • 특정 합을 가지는 경로 찾기
  • 두 노드 사이의 경로
• 구조 변경 문제
  • 트리 뒤집기
  • 서브트리 찾기
  • 트리 합치기

 

4단계: 실전 학습 순서

1. 기본 순회 구현
   • 각 순회를 재귀/반복 두 방식으로 구현
   • 추천문제: 백준 1991
2. 깊이/높이 문제
   • 추천문제: 리트코드 104
3. 경로 탐색 문제
   • DFS를 활용한 경로 찾기 문제들
   • 백트래킹과 결합된 문제들
4. 복합 문제

 

5단계: 문제 접근 전략

1. 이 문제는 어떤 순회가 필요한가?
   • 값을 먼저 처리? -> 전위
   • 왼쪽 처리 후 값 처리? -> 중위
   • 자식들 처리 후 값 처리? -> 후위
2. 전체 트리를 봐야 하나, 부분만 봐야 하나?
   • 전체 -> 순회 기반 접근
   • 부분 -> 조건부 탐색
3. 상향식인가, 하향식인가?
   • 하향식: 부모에서 자식으로 정보 전달
   • 상향식: 자식에서 부모로 결과 전달

 

실습 추천 문제 순서

• 입문
  • 리트코드 144, 94, 145 (기본순회)
  • 리트코드 104 (최대깊이)
  • 리트코드 226 (트리 뒤집기)
• 중급
  • 리트코드 112 (경로 합 판별)
  • 리트코드 110 (균형 트리 판별)
  • 리트코드 236 (공통 조상)
• 고급
  • 리트코드 124 (최대 경로 합)
  • 리트코드 297 (직렬화/역직렬화)