[LeetCode 617] Merge Two Binary Trees (Java)

🚀 문제 분석

• 목표: 두 개의 이진 트리를 하나로 합칩니다.
• 규칙:
  • 두 노드가 겹치면 값을 더합니다.
  • 한쪽 노드만 존재하면 존재하는 노드를 그대로 사용합니다.
• 핵심: 두 트리를 동시에 순회하면서, 새로운 구조를 재귀적으로 형성해야 합니다.

💡 해결 전략: 재귀를 이용한 트리 합성

트리 재귀의 정석적인 접근법인 "나부터 처리하고 자식에게 떠넘기기"를 활용합니다.

1. 기저 사례 (Base Case) - 재귀의 핵심:
   • 한쪽 트리가 null이라면? 고민할 것 없이 반대편 트리(노드와 그 하위 서브트리 전체)를 통째로 반환합니다. 이 처리가 수많은 if-else를 줄여주는 핵심 포인트입니다.
2. 값 합산: 두 노드가 모두 존재한다면 값을 더해 새로운 노드를 생성합니다.
3. 자식 병합:
   • 현재 노드의 왼쪽 자식은 mergeTrees(root1.left, root2.left)의 결과물입니다.
   • 현재 노드의 오른쪽 자식은 mergeTrees(root1.right, root2.right)의 결과물입니다.

💻 구현 코드 (Java)

public class Solution_Leetcode_617 {

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 한쪽이 없으면 있는 쪽을 그대로 리턴 (서브트리 통째로 연결)
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        // 두 노드 값을 합쳐서 새로운 노드 생성
        // 왼쪽, 오른쪽 자식에 대해 다시 병합 재귀 호출
        TreeNode left = mergeTrees(root1.left, root2.left);
        TreeNode right = mergeTrees(root1.right, root2.right);
        
        return new TreeNode(root1.val + root2.val, left, right);
    }
}

🧐 기술적 고찰

• 불변성(Immutability): 위 코드는 new TreeNode를 사용하여 새로운 트리를 구성합니다. 원본 트리를 수정(In-place)하지 않으므로 데이터 안정성 측면에서 우수합니다.
• 효율적인 가지치기: root1이 null일 때 root2를 리턴하는 순간, 그 하위의 모든 자식 노드들은 더 이상 탐색하지 않고 그대로 붙습니다. 이는 전체 노드를 일일이 방문하지 않아도 되게 하는 중요한 최적화입니다.
• 시간 복잡도: 두 트리 중 노드 수가 적은 트리의 노드 수만큼 방문하므로 $O(\min(N, M))$입니다.