[LeetCode] 226. Invert Binary Tree - 문제 해석 및 Java풀이

코딩테스트 문제를 푸는데 어렵지만 재밌는 문제도 있지만, 실무에서 도움이 될만한 문제일까? 싶은 의구심도 많이 들었다. 진짜 문제 푸는데 비상한 사람들이 많다는 것도 많이 느끼면서 실무적으로 정말 잘하는 사람인데 코딩테스트에서 잘 못 푼사람이 있지 않을까 하고 GPT에게 사례를 찾아봐달라고 하였다.

 

gpt의 답변

 

해당 사건을 자세히 다룬 블로그들이 많았고, 어떤 문제였는지 저런 대단한 개발자분이 풀지 못 하였던 문제가 무엇인지 궁금하여 찾아보았다. 찾아본 결과 해당 사건 때문인지는 모르겠지만 엄청 유명한 문제인것 같았다. 

 

문제 : Invert Binary Tree (이진 트리 반전)

Given the root of a binary tree, invert the tree, and return its root.

주어진 root는 이진트리이며, 트리를 반전하여 반환해라.

 

Example 1:

 

Example 2:

 

문제 풀이 1 - Stack

문제를 보자마자, 노드는 자식 노드 정보를 가지고 있으므로 위에서부터 차례대로 자식 노드끼리 변경하면서 내려가면 되겠다는 생각이 떠올랐다.

 

고민한 결과 루트 노드에서 하위 모든 자식 노드를 변경해야 하므로 단순히 순차적으로 처리하기위해 하위 노드들을 저장한 뒤, 하나씩 꺼내어 변경하는 방식이 적절하겠다고 판단했다.

 

이때, 하나씩 꺼내서 처리하고, 다 사용하면 비워지는 자료구조가 필요했는데, 예상했겠지만 바로 스택(Stack)이 적절하다고 생각했다. 큐(Queue)를 사용할 수 도 있지만.. 로직은 동일할 것 같다.

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        
        Stack<TreeNode> nodeStack = new Stack();
        nodeStack.push(root);

        while(!nodeStack.isEmpty()) {   // 더이상 전환할 노드가 없을때 까지
            TreeNode node =  nodeStack.pop(); // 스택에 저장된 노드 반환

            // 좌우 노드 서로 교환
            TreeNode temp = node.right;
            node.right = node.left;
            node.left = temp;

            // 우측 노드가 없을때 Stack에 추가하지 않음
            if(node.right != null) {
                nodeStack.push(node.right);
            }

            // 좌측 노드가 없을때 Stack에 추가하지 않음
            if(node.left != null) {
                nodeStack.push(node.left);
            }
        }

        return root;
    }
}

 

문제 풀이 2 - 재귀함수

다른사람들이 푼 방식도 찾아보았는데 재귀함수를 많이 사용했다는 것을 알게 되었다. 생각해 보니 노드를 교환하는 메소드를 만들고 하위 노드들을 자기 자신을 호출하여 모든 자식노드들을 전환할 수 있었다.

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
       if (root == null) {
            return null;
        }
        
        // 왼쪽, 오른쪽 자식 교환
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        
        return root;
    }
}

 

마무리

개인적으로 굉장히 재미있게 풀었던 문제였다. 놀라웠던 점은 대부분의 사람들이 재귀 함수를 사용해 풀었다는 것이다. 실제로 "트리 문제는 재귀!" 라는 문구도 보았는데, 다음에 트리 문제가 나오면 나 역시 재귀 함수 풀이도 고려해 봐야겠다고 생각했다. (단, 간단한 트리에서는 괜찮지만, 깊이가 매우 깊은 트리에서는 스택 오버플로우에 주의해야 한다 글을 보아 해당 사항을 함께 기억해야겠다.)

 

정말 잘하는 사람들이 많은 것 같다. 내가 생각했던 대로 큐(Queue) 를 이용해 풀이한 사람도 있었고, 비트 연산으로 해결한 사람, 배열에 저장한 후 반전시켜 해결한 사람 등 다양한 접근 방식이 있었다. 다른 사람들의 풀이를 하나하나 읽어가며 새로운 시각을 배우는 과정이 무척 재미있었다.