[LeetCode/JAVA] 617. Merge Two Binary Trees

https://github.com/ROUTINE-STUDY/Algorithm

ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/merge-two-binary-trees/

Merge Two Binary Trees - LeetCode

문제 설명

출처 : LeetCode

두 개의 이진트리가 주어집니다.
두 트리를 병합한다고 상상하고, 같은 위치에 있는 트리의 값은 합산해서 반환합니다.
즉, 병합된 이진 트리를 반환합니다.

풀이 방법

주어진 두 개의 이진 트리 중 한 개의 트리(root1)를 기준으로 잡고 비교하는 방식을 사용하였습니다.
1. 루트는 무조건 존재하므로 각자의 큐에 2개의 루트 노드를 삽입합니다.
2. root1에 root2의 값을 누적하여 더해줍니다.
3. 각자 큐에서 노드를 꺼낸 뒤 2개의 노드의 left 노드가 모두 존재하면 큐에 모두 삽입한 뒤 root1의 좌우 값을 더해줍니다.
4. 만약 root2에만 있다면 root2의 값을 1로 저장합니다. (root1만 있을 땐 기준이기 때문에 그대로 유지)
5. 3~4 번을 동일하게 right 노드도 확인합니다.
6. 기준이 되었던 root1을 반환합니다.

내 코드(JAVA)

 

// 하나의 TreeNode를 기준으로 잡고 비교하여 검사
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

    if(root1 == null && root2 == null) return null;
    else if(root1 != null && root2 == null) return root1;
    else if(root1 == null && root2 != null) return root2;

    Queue<TreeNode> q = new LinkedList<>();
    Queue<TreeNode> q2 = new LinkedList<>();

    // root 는 무조건 존재하므로 세팅
    q.offer(root1);
    q2.offer(root2);
    root1.val += root2.val;

    while(!q.isEmpty()) {
        int size = q.size();

        for(int i=0; i<size; i++) {
            TreeNode node1 = q.poll();
            TreeNode node2 = q2.poll();

            // 둘 다 있거나 or 한 쪽만 있거나
            // left가 두 Tree에 모두 존재하면 큐에 모두 삽입 후 left.val 세팅
            if(node1.left != null && node2.left != null) {
                q.offer(node1.left);
                q2.offer(node2.left);

                node1.left.val += node2.left.val;
            } else if(node1.left == null) { // 한 쪽만 있으면 있는 쪽 세팅
                node1.left = node2.left;
            }

            // 로직은 위와 동일함(right)
            if(node1.right != null && node2.right != null) {
                q.offer(node1.right);
                q2.offer(node2.right);

                node1.right.val += node2.right.val;
            } else if(node1.right == null) {
                node1.right = node2.right;
            }
        }
    }

    return root1;
}

스터디 피드백 내용

1. 큐를 하나로 통일하여 사용이 가능합니다. 큐는 담는 역할만 할 뿐이고 무조건 2개씩 뽑아야 함
2. 첫 번째 조건문에서 불필요한 조건을 삭제할 수 있습니다.

 

public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
	
    // root1 == null && root2 == null이 성립하지 않으면
    // root1, root2 둘다 널이 아니거나 하나만 null인 경우가 되겠습니다.
    if(root1 == null && root2 == null) return null;
    else if(root1 == null) return root2;
    else if(root2 == null) return root1;
	
    // 큐를 하나로 통합 가능, 무조건 2개씩 넣고 2개씩 꺼내야 함
    Queue<TreeNode> q = new LinkedList<>();

    q.offer(root1);
    q.offer(root2);
    root1.val += root2.val;

    while(!q.isEmpty()) {

        TreeNode node1 = q.poll();
        TreeNode node2 = q.poll();

        if(node1.left != null && node2.left != null) {
            q.offer(node1.left);
            q.offer(node2.left);

            node1.left.val += node2.left.val;
        } else if(node1.left == null) {
            node1.left = node2.left;
        }

        if(node1.right != null && node2.right != null) {
            q.offer(node1.right);
            q.offer(node2.right);

            node1.right.val += node2.right.val;
        } else if(node1.right == null) {
            node1.right = node2.right;
        }
    }

    return root1;
}

 

조건문을 짤 때 조금 더 생각한다면 불필요한 코드를 줄일 수 있습니다.

문제를 잘 파악하거나 리팩토링 할 때 불필요 변수를 선언하지 않았는지 더 확인해야 할 것 같습니다.