Recursive HashMap 기반 Binary Tree Bottom-up 순회 구현

Leetcode # 107. Binary Tree Level Order Traversal II

Hector Williams2026년 4월 15일3분beginner

AI 요약

Context

Binary Tree의 노드를 리프 노드부터 루트 노드 순으로 level-by-level 추출하는 Bottom-up Traversal 구현 필요. 일반적인 Level Order Traversal의 결과 순서를 역전시켜 데이터 구조를 재구성하는 것이 핵심 과제임.

Recursive function을 활용해 각 노드의 depth(level) 정보를 추적하는 하향식 탐색 수행
HashMap<Integer, List> 구조를 채택하여 level별 노드 값을 그룹화함으로써 비연속적인 레벨 데이터 통합
서브트리 간의 HashMap merge 로직을 통해 서로 다른 브랜치에서 발생한 동일 레벨 노드들을 단일 리스트로 병합
탐색 완료 후 HashMap의 keySet을 기반으로 리스트를 생성하고 Collections.reverse()를 통해 최종적인 Bottom-up 순서 보장
재귀 호출 시 level 인자를 전달하여 트리 깊이에 따른 데이터 매핑 정확도 확보

실천 포인트

1. 계층 구조 데이터의 역순 출력이 필요할 때, 전체 구조를 Map에 저장 후 Reverse 하는 전략 검토

2. Recursive approach 사용 시- State(level) 전달을 통한 데이터 그룹화 가능 여부 확인

3. 대규모 트리 구조에서는 HashMap merge 시 발생하는 시간 복잡도 및 메모리 오버헤드 분석 필요

태그