99클럽 코테 스터디 13일차 TIL + 이진 트리, [leetcode] Invert Binary Tree

✨ 문제 

Invert Binary Tree

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

 

https://leetcode.com/problems/invert-binary-tree/description/

 

 

 

✨ 개념

이진 트리

- 분할 정복 탐색 알고리즘으로 빠른 속도로 탐색 가능

- 모든 노드가 2개의 서브 트리를 갖는 트리. 서브트리는 공집합일 수 있음.

- 모든 노드가 최대 2개의 자식 노드가 존재할 수 있음.

- 모든 노드의 차수가 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;
 *     }
 * }
 */
 

public class InvertBinaryTree {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return root;
            
        if (root.left != null)
            invertTree(root.left);
        if (root.right != null)
            invertTree(root.right);
        if (root.left == null && root.right == null)
            return root;

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        return root;
    }
}

 

오늘의 문제는 루트 노드를 제외한 모든 트리를 invert하는 것이다.

 

일단 root가 null인 경우 root를 그대로 반환하도록 하였다.

그리고 root가 자식 노드를 갖고 있지 않을 경우 단말노드이므로 root를 그대로 반환한다. 단말노드가 아닌 경우 왼쪽 자식노드가 있는지 확인 후 재귀호출한다. 마찬가지로 오른쪽 자식노드도 null이 아닌 경우 재귀호출을 한다.

왼쪽 자식 노드와 오른쪽 자식 노드가 모두 null인 경우 단말노드이므로 root를 그대로 리턴한다.

그 다음 임시변수 temp를 만들어 왼쪽과 오른쪽을 교환한다.

 

최근 며칠 동안 트리 문제를 풀었는데 처음 트리를 사용하려 했을 때 어떻게 사용해야하는지 감도 안잡히고 이해가 안갔었다. 근데 다른 코드들을 보니 엄청 간결해서 이렇게 간단하다고? 했는데 아마 재귀호출을 제대로 이해하지 못해서 어려웠던 것 같다. 오늘에서야 조금 이해가 된 것 같다. 이제 내가 이해했으니 아마 또 새로운게 나오지 않을까 싶다. 얼마나 재밌을까 ? 😊