[ Tree ] 226. Invert Binary Tree (Java)

 

 

1. 문제

Given the root of a binary tree, invert the tree, and return its root.
이진 트리인 root가 주어지고 해당 트리의 순서를 뒤집어 반환하라

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

 

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• 100 <= Node.val <= 100

 

 

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;
        if(root.right != null){
            root.left = invertTree(root.right);
        }else{
            root.left = null;
        }
        
        if(temp != null){
            root.right = invertTree(temp);
        }else{
            root.right = null;
        }
        temp = null; // 이 부분을 썼을 때, 안 썼을 때의 차이가 

        return root;
    }
}

 

root의 좌우가 null인 것은 제일 아래 node이기 때문에 더 이상 연산을 할 필요가 없으므로
if 문의 조건을 null이 아닌 경우로 걸어서 진행이 되도록 한다.

 

 

이 사진처럼 자식이 하나만 있는 root도 있고
그 자식이 right에 위치한 것인지
left에 위치한 것인지 알지 못하기 때문에
else를 걸어서 null일 땐 null로 두도록 세팅해 준다.

 

그러고 나서 재귀용법을 사용하여 제일 아래 node까지 타고 타고 내려갈 수 있게 해 준다.

 

마지막에 temp 트리노드를 null처리를 했을 때와 아닐 때의 메모리 사용량이 꽤나 차이가 났다.

 

null로 만들기 전에는

• runtime : 0ms
• beats : 100%
• memory : 40.3MB
• beats : 52.23%

이렇고

null로 만든 후에는 아래와 같다.

• runtime : 0ms
• beats : 100%
• memory : 39.9MB
• beats : 92.67%

 

변수를 null로 만들어두면 나중에 가비지 컬렉터가 먹어치우기 때문에
메모리 사용량을 조금이나마 줄일 수 있다고 배웠다.

 

이제까지 문제 푼 것들이 연습이 된 것인지
아니면 트리 문제가 유독 나한텐 쉬웠던 것인지는 모르겠으나
이번 문제는 10분 만에 풀었다 키키키

 

submit도 2번 만에 Accepted 됐다!!
와씨 너무 신난다!!!!!!