LeetCode 617(Merge Two Binary Trees, java)

0. 문제

https://leetcode.com/problems/merge-two-binary-trees/

Merge Two Binary Trees - LeetCode

 

 

1. 문제 설명

- 문제에서 이진트리 2개(root1, root2)가 주어진다.

- 두 이진트리를 병합하여 하나의 이진트리를 반환하는 것이 문제의 핵심이다.

 

 

2. 문제 해설

a) 첫 번째 접근

- 이 문제는 두 트리의 노드를 탐색하여, 각 노드의 값을 병합하는 과정을 반복해서 수행한다.

- 트리의 탐색과 노드 값의 병합이라는 반복 연산이 필요하므로, 재귀 함수를 이용하여 해결할 수 있다.

 

 

b) 두 번째 접근

- 우선 계산된 노드의 값을 담을 트리 객체를 생성한다. 이는 마지막에 반환될 객체다.

- root1이 없다면 root2를, root2가 없다면 root1의 노드를 사용하면 된다.

- 만약 root1과 root2가 모두 존재하는 경우, 두 노드의 값을 합친 새로운 노드를 생성하면 된다.

 

- 이 과정을 재귀로 풀어내면 된다.

- 다음 코드를 보면서 이해해보자.

 

 

3. 정답 코드

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        
        TreeNode result = new TreeNode(root1.val + root2.val);
        result.left = mergeTrees(root1.left, root2.left);
        result.right = mergeTrees(root1.right, root2.right);
        
        return result;
    }
}