Invert Binary Tree

풀이

간단한 이진트리를 뒤집는 문제임

주어지는 이진트리는 left, right로 구분되어 있음

핵심 풀이과정은 다음과 같음

1. 트리의 root를 기준으로 left, right를 교체
2. 레벨을 하나씩 높여가며 root를 새로 정의하고 1번을 수행
3. 위 과정을 root가 null일때까지 반복

그래서 코드는 다음과 같음

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(!root) return nullptr;

        auto l = root -> left ? root -> left : nullptr;
        auto r = root -> right ? root -> right : nullptr;

        root -> left = r;
        root -> right = l;

        invertTree(l);
        invertTree(r);

        return root;
    }
};

기본적으로 이진트리는 재귀를 통해 접근하는게 쉬운거같음

근데 재귀는 잘못 다루면 stack overflow가 터지므로 직접 root를 그래프로 보고, bfs나 dfs를 통해 푸는 방법도 알려줌

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        std::queue<TreeNode*> q;
        q.push(root);

        while(q.size() > 0)
        {
            TreeNode* root = q.front();
            q.pop();

            if(!root) continue;

            auto l = root -> left ? root -> left : nullptr;
            auto r = root -> right ? root -> right : nullptr;

            root -> left = r;
            root -> right = l;

            q.push(l);
            q.push(r);
        }

        return root;
    }
};

Muy facil!
베리 이지!