루트 방문 위치로 구분
전위는 루트를 먼저, 중위는 왼쪽 뒤, 후위는 자식 처리 뒤에 결과에 넣습니다.
트리 순회 방문 시점
전위, 중위, 후위, 레벨 순회는 모두 O(N)이지만 값을 기록하는 시점과 보조 구조가 다릅니다. 요구 출력부터 고정해야 합니다.
스택에 되돌아올 지점을 저장
재귀를 반복으로 바꿀 때는 현재 노드와 처리 단계가 스택에 함께 보존되어야 합니다.
큐 크기로 층을 나눈다
BFS는 현재 레벨 개수를 먼저 고정하면 다음 레벨과 결과 묶음이 섞이지 않습니다.
방문 누락을 줄이는 반례
리프자식이 없는 노드에서도 결과 기록 시점이 정확한지 확인합니다.
편향한쪽으로 긴 트리에서 재귀 깊이와 반복 스택 순서를 비교합니다.
출력순회 결과를 저장할지 즉시 처리할지 메모리 사용량까지 함께
봅니다.