두 이진 트리 병합: 코딩 문제 설명

I’m happy to translate the article for you, but I’ll need the full text you’d like translated. Could you please paste the content (excluding the source line you already provided) here? Once I have the text, I’ll translate it into Korean while preserving the original formatting, markdown, and any code blocks or URLs.

문제 개요

Merge Two Binary Trees는 두 재귀 구조를 깔끔하게 결합할 수 있는지 확인하는 트리 순회 문제입니다. 두 이진 트리의 루트가 주어집니다. 간단한 규칙에 따라 두 트리를 하나의 이진 트리로 병합하는 것이 목표입니다.

• 같은 위치에 두 노드가 겹치는 경우, 병합된 트리는 두 값의 합을 갖는 노드를 포함해야 합니다.
• 한 트리에는 존재하고 다른 트리에는 존재하지 않는 노드가 있을 경우, 병합된 트리는 기존 노드와 그 전체 서브트리를 재사용해야 합니다.

실제로는 두 트리를 서로 겹쳐 놓은 것으로 생각할 수 있습니다. 두 트리 모두에 노드가 있는 곳에서는 값을 더하고, 한 트리만에 노드가 있는 곳에서는 해당 노드를 그대로 유지합니다.

이 문제는 인터뷰에서 흔히 등장하는데, 재귀, 기본 사례, 그리고 값보다 구조에 대한 사고 능력을 테스트하는 깔끔한 방법이기 때문입니다.

재귀가 여기서 자연스럽게 맞는 이유

이진 트리는 재귀적인 데이터 구조입니다. 각 노드는 왼쪽 서브트리와 오른쪽 서브트리를 가지고 있으며, 그 서브트리들 자체도 이진 트리입니다.

병합 규칙이 모든 대응되는 노드 쌍에 적용되기 때문에 가장 직관적인 해결책도 재귀적입니다. 현재 노드 쌍에 대해 병합을 수행하고, 그 다음 왼쪽 자식을 병합하고, 마지막으로 오른쪽 자식을 병합합니다.

이러한 “각 레벨에서 동일한 작업을 수행한다”는 패턴은 바로 재귀가 설계된 목적입니다.

핵심 병합 로직

어떤 위치에서든 병합 결정은 세 가지 경우로 나뉩니다:

1. Both nodes are null – 해당 위치의 병합 결과는 null입니다.
2. One node is null – 병합 결과는 단순히 null이 아닌 노드가 됩니다. 추가할 것이 없으며, 문제 설명에 따라 기존 서브트리를 유지합니다.
3. Both nodes are present – 두 노드 값의 합인 값을 갖는 병합 노드를 생성합니다. 그런 다음 왼쪽 자식을 병합하여 병합 노드의 왼쪽 자식을 만들고, 오른쪽 자식을 병합하여 병합 노드의 오른쪽 자식을 만듭니다.

이것이 전체 규칙이며, 트리 전체에 걸쳐 반복됩니다.

더 많은 코딩 문제 해결책을 탐색하고 싶으신가요? Maximum Product of Three Numbers와 Top K Frequent Words를 확인해 보세요.

구현을 생각하는 두 가지 방법

면접관은 보통 두 접근법 중 어느 것이든 명확히 설명하면 괜찮아합니다.

• 새 트리 만들기 – 겹치는 부분마다 새로운 노드를 생성하고 병합된 자식을 재귀적으로 연결합니다. 이렇게 하면 원본 트리가 변경되지 않아 부작용을 피하고 싶을 때 좋은 특성입니다.
• 제자리에서 병합 – 보통 첫 번째 트리에서 수행합니다. 두 노드가 모두 존재하면 두 번째 노드의 값을 첫 번째 노드에 추가하고 자식을 재귀적으로 병합하며 가능한 한 노드를 재사용합니다. 겹치는 부분에 대해 새로운 노드를 만들지 않으므로 메모리 효율이 더 높을 수 있습니다.

개념적으로 두 접근법 모두 동일한 병합 규칙을 따릅니다. 차이점은 기존 트리를 변형하느냐 새 트리를 구축하느냐에 있습니다.

솔루션이 올바른 이유

정확성은 병합된 트리의 각 위치가 입력 트리의 동일한 위치에 있는 노드들에만 의존한다는 사실에서 비롯됩니다.

• 두 트리 모두 해당 위치에 노드가 있으면, 두 값을 더해야 합니다.
• 하나만 존재한다면, 그 노드를 그대로 유지해야 합니다.

재귀 호출을 통해 동일한 결정 규칙이 왼쪽 서브트리와 오른쪽 서브트리 모두에 일관되게 적용되며, null에 도달할 때까지 계속됩니다.

각 노드 위치가 정확히 한 번씩 처리되므로, 노드를 놓치거나 서브트리를 중복할 위험이 없습니다. 병합 연산은 두 트리의 구조를 유지하면서 겹치는 부분에서는 값을 결합합니다.

간단히 말한 성능

트래버설은 두 트리 중 하나에 존재하는 각 노드를 방문하므로 실행 시간은 두 트리의 총 노드 수에 비례합니다.

공간 사용량은 접근 방식에 따라 다릅니다:

• 새 트리 만들기 – 겹치는 부분에 대해 새 노드를 할당하므로 메모리를 더 많이 사용합니다.
• 제자리 병합 – 추가 메모리는 대부분 재귀 호출 스택에 제한됩니다.

두 경우 모두 재귀 깊이는 트리의 높이에 연결됩니다.