LeetCode/617. Merge Two Binary Trees

굳이 새거 만들어서 하려면 머리가 아프다. 주어진 2개 중 하나를 골라서 다른 녀석을 합쳐주면 편하다.

하지만, 추후 공간 절약을 위해 두 녀석을 delete 해버리고 새로운 녀석 하나만 가지고 있는 것이 좋다. 그러면 굳이 새로 코드를 짤 필요 없이 root2에서 떼올때 root2->left나 right를 nullptr로 밀어주면 될거같다.

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr)
            return root2;
        if(root2==nullptr)
            return root1;
        
        //양쪽 다 nullptr이 아니다
        //진입해서 만들자
        merge(root1, root2);
        
        return root1;
    }
    
    void merge(TreeNode* root1, TreeNode* root2)
    {
        //진입했으면 주어진 위치의 노드들 합친다
        root1->val = root1->val + root2->val;
        //나와 같은 위치를 탐색하도록 하는 것이 중요하다
        //우선 왼쪽을 본다, 둘 다 있으면 합친다
        if(root1->left!=nullptr && root2->left!=nullptr)
        {
            //왼쪽이 있다면 합치라고 한다
            merge(root1->left, root2->left);
        }
        //오른쪽을 본다, 둘 다 있으면 합친다
        if(root1->right!=nullptr && root2->right != nullptr)
        {
            //있다면 합치라고 한다
            merge(root1->right, root2->right);
        }
        
        //다시, 왼쪽을 봤는데 나는 없고 쟤는 있으면 가져온다.
        //얕은 복사 해주면 위쪽에서 가져오면 아래쪽은 자동으로 딸려온다.
        if(root1->left==nullptr && root2->left!=nullptr)
        {
            root1->left = root2->left;
        }
        
        //오른쪽도 마찬가지로
        if(root1->right == nullptr && root2->right != nullptr)
        {
            root1->right = root2->right;
        }
        
        return;
    }
};