[Easy] 226. Invert Binary Tree / 구글 코딩 테스트 기출 문제

이번 문제는 구글 코딩 테스트로 굉장히 유명한 문제이다. 이 문제가 유명해진 데에는 한 가지 이유가 있다. 맥(Mac)을 사용하는 개발자라면 누구나 사용해 봤을 법한 Homebrew (MacOS 패키지 관리자)를 개발한 사람으로 유명한 Max Howell은 2015년 구글과 입사 면접을 보는데, 면접 문제에서 binary tree를 invert하는 문제가 나왔지만 결국 풀지 못해 면접에서 떨어지게 된다. 

그 후에 Max Howell은 자신의 트위터에 

"구글: 90%의 구글 엔지니어들은 네가 개발한 소프트웨어를 사용하지만, 너는 binary tree invert하는 것도 화이트보드에 풀지 못하기 때문에 꺼져라" 와 같은 글을 올리며 자신은 굉장히 많은 사람들이 사용하는 소프트웨어를 개발했지만 고작 코딩 테스트 문제 하나를 풀지 못해 자신을 거절한 구글의 면접 프로세스의 아이러니함을 언급한다. 이 사건으로 인해 이 문제는 개발자들 사이에서 유명해지는 계기가 됐다.

#문제 설명

이번 문제의 컨셉은 굉장히 간단하다. Binary Tree의 root가 주어지고, 그 트리의 왼쪽과 오른쪽을 거울처럼 바꾸어 놓으면 된다.

#문제 풀이

class Solution {
    public TreeNode invertTree(TreeNode root) {
     if(root == null){
         return null;
     }
        TreeNode temp = root.left;
        root.left= root.right;
        root.right = temp;

     invertTree(root.left); //먼저 tree의 왼쪽부분 traverse
     invertTree(root.right); //다음 tree의 오른쪽부분 traverse

     return root;

    }
}

이 문제를 풀기 위해선 주어진 트리를 재귀적으로 traverse해야 한다. invertTree(root.left)와 invertTree(root.right)가 자기자신의 함수를 계속 call하면서 재귀적으로 tree의 왼쪽 부분 먼저, 그 다음 오른쪽 부분을 traverse하고 있다. 그 다음 우리는 tree를 traverse하면서 왼쪽과 오른쪽을 바꿔야 하기 때문에, temp변수을 root.left로 설정하고, left node를 right node로 설정한 다음 마지막으로 right node를 left node로 설정하여 두 개의 노드의 값을 바꿀 수 있다. 마지막으로 이 풀이의 base case는 root가 null일 때, 즉 트리의 끝에 다다랐거나 더 이상 나아갈 수 없을 때이다.