[LeetCode C++] 617. Merge Two Binary Trees

⭐️ 난이도

 

Easy

---

⭐️ 문제

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

Merge Two Binary Trees - LeetCode

You are given two binary trees root1 and root2.

이진 트리 root1과 root2가 주어진다.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

하나의 트리를 또 다른 트리 위에 올렸다고 가정했을 때, 몇몇 노드는 겹칠 것(overlap)될 것이고, 다른 노드들은 그렇지 않을 것이다.

You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

당신은 두 개의 트리를 병합(merge)하여 새로운 이진 트리를 만들어야 한다. 합치는 룰은 다음과 같다.

만일 두 개의 노드가 겹친다면 합병된 노드의 값은 두 노드의 값(value)의 합로 한다.

서로 겹치지 않는다면 null이 아닌 노드의 값이 합병된 노드의 값이 될 것이다.

Return the merged tree.

합병한 트리를 구하라.

Note: The merging process must start from the root nodes of both trees.

주의: 병합하는 과정은 반드시 두 트리의 root에서부터 시작해야 한다.

 

 

---

⭐️ Follow-up

 

X

 

---

⭐️ Idea flow

 

두 개의 이진 트리를 합치는데 반드시 루트 노드부터 시작해야 한다.

그러므로 루트에서 시작해서 재귀적으로 left child와 right child를 확인한다.

 

같은 레벨을 유지하면서 value 값을 확인하고 각 노드의 값을 더해서 새로운 트리의 노드의 값에 적용하면 된다.

주의해야 할 점은 해당 노드의 자식 노드가 null일 때이다.

 

노드의 값을 선정 할 때 어떤 노드가 null이라면 해당 값을 0으로 처리하고 더한다.

문제는 재귀로 자식 노드를 전달할 때인데 만일 현재 자신이 null이라면, 왼쪽/오른쪽 자식이 존재하지 않으므로

무작정 접근을 하면 exception이 뜰 것이다.

 

따라서 조건문을 통해서 root1 혹은 root2 중 null이 존재하는지 확인하고, null 쪽은 자식이 아니라 본인을 넘김으로써

exception이 뜨지 않도록 해야한다.

 

 

---

⭐️ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void merge(TreeNode* root1, TreeNode* root2, TreeNode* &mergedTree){
    	// root1, root2 모두 null이면 return
        if(!root1 && !root2)    return;

        else if(!root1 && root2){ // root1만 null인 경우
            mergedTree = new TreeNode(root2->val);
            merge(root1, root2->left, mergedTree->left);
            merge(root1, root2->right, mergedTree->right);
        }
        else if(root1 && !root2){ // root2만 null인 경우
            mergedTree = new TreeNode(root1->val);
            merge(root1->left, root2, mergedTree->left);
            merge(root1->right, root2, mergedTree->right);
        }
        else{ // 둘 다 null이 아닌 경우
            mergedTree = new TreeNode(root1->val + root2->val);
            merge(root1->left, root2->left, mergedTree->left);
            merge(root1->right, root2->right, mergedTree->right);
        }        
    }
    
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        TreeNode* mergedTree(nullptr);
        merge(root1, root2, mergedTree);
        
        return mergedTree;
    }
};