리트코드 - 226. Invert Binary Tree

리트코드 - 226. Invert Binary Tree

출처 - https://leetcode.com/problems/invert-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

이진 트리의 루트가 주어지면 트리를 반전하고 루트를 반환합니다.

의사코드

함수 invertTree if (root == null)     null 리턴 if (root.left != null)     if (root.right == null)         root.right = root.left         root.left = null     else         TreeNode tempNode = new TreeNode         tempNode = root.left         root.left = root.right         root.right = tempNode else     if (root.right != null)         root.left = root.right         root.right = null invertTree(root.left) invertTree(root.right)

 

풀이코드

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        if (root.left != null) {
            if (root.right == null) {
                root.right = root.left;
                root.left = null;
            } else {
                TreeNode tempNode = new TreeNode();
                tempNode = root.left;
                root.left = root.right;
                root.right = tempNode;  

            }
        } else {
            if (root.right != null) {
                root.left = root.right;
                root.right = null;
            }
        }
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}

 

코드설명

함수를 재귀적으로 이용하는 방법이다.

노드가 주어지면 먼저 null인지 판단하고, left와 right를 확인하여 조건에 따라 바꿔주면 된다.

 

1. node의 한쪽(왼쪽이든 오른쪽이든)만 값을 가지는 경우

2. node가 자식노드를 가지지 않는 경우

3. node가 자식노드를 가지는 경우

 

1번의 경우 값을 가진 노드를 반대편으로 옮겨주고, 원래 노드는 null로 바꿔주면 된다.

2번의 경우는 별도로 아무 처리 하지 않아도 된다.

3번의 경우 두 노드를 직접 다루면 엉키기 쉽기 때문에 TreeNode를 하나 만들어서 swap 해준다.

 

코테에서 많이 사용하는 temp를 이용하여 a, b 값을 바꿔주는 것을 Node에 적용해봤다.

이렇게 해서 노드 자식들이 바뀌었으면 왼쪽 노드, 오른쪽 노드로 이동하면서 동일한 작업을 해준다.

상위에서 하위로 함수가 호출되는 재귀적인 구조이다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

다른코드

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

나름 괜찮게 풀었다고 생각했는데 다른 코드를 보고 충격을 먹었다.

나랑 진행방식은 똑같은데, 가장 큰 차이는 처음의 root == null을 써먹느냐 아니냐가 달랐다.

swap을 재귀방식으로 구현한 것은 눈에 두고 익혀야겠다.

 

어제 풀었는데 임시저장만 시켜놓고 글을 안올렸다...

 

 

정리

트리를 재귀방식으로 탐색하는 방법.