ch14-4(leetcode 226). 이진 트리 반전

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 226번 ( https://leetcode.com/problems/invert-binary-tree/ )

 

✅교재를 참고하지 않은 풀이

 

📌DFS

 

이진 트리의 root 노드가 입력으로 주어질 때, 이진 트리를 좌우로 반전시키고 해당 트리의 root 노드를 리턴하는 문제이다. 

좌우로 반전시키려면 root 노드를 기준으로 왼쪽 subtree와 오른쪽 subtree를 바꾸면 된다. 

 

root 노드를 기준으로 모든 노드를 좌우 반전하려면 결국은 leaf 노드에서부터 작업을 시작해야 한다. 만약 leaf 노드까지 가지 않고 root 노드 바로 아래 레벨의 노드만 바꾼다면 아래 레벨의 노드들은 반전되지 않기 때문이다. 

 

예를 들어 다음과 같은 이진 트리를 입력받았다고 해 보자. 

만약 root 노드 바로 아래 레벨의 노드들 위치만 바꾸게 된다면 트리는 이런 모양이 된다. 

그러나 좌우 반전 트리는 모든 레벨의 노드들의 위치가 바뀌어야 하므로 위의 방법으로는 풀 수 없다. 좌우 반전은 아래처럼 7, 2 노드의 하위 노드들의 위치도 모두 바뀌어야 한다. 

따라서 재귀 함수를 사용해서 DFS 탐색으로 leaf 노드를 찾은 뒤, 해당 노드부터 다시 위 레벨로 올라오면서 자기 아래에 있는 두 노드의 위치를 바꾸는 방식으로 구현한다. 

 

또한 파이썬이 아닌 다른 언어(자바나 C언어)에서는 두 변수의 값을 바꿀 때 임시로 다른 변수 하나를 추가하는 방법을 쓴다. 

int a = 1;
int b = 2;

int temp = a;
a = b;
b = temp;

 

그러나 파이썬에서는 다중 할당을 사용할 수 있다. 

a = 1
b = 2

a, b = b, a

 

전체 코드는 다음과 같다. 

class Solution(object):

    def invertTree(self, root):
    
        def dfs(node):
            if not node:
                return
                
            dfs(node.left)
            dfs(node.right)
            
            if node.left and node.right:
                node.left, node.right = node.right, node.left
            elif node.left:
                node.left, node.right = None, node.left
            elif node.right:
                node.left, node.right = node.right, None
            
        head = root
        dfs(root)
        return head

 

✅교재를 참고한 풀이

 

📌재귀를 사용한 파이썬 방식

 

위의 DFS 방식을 그대로 사용하고 코드를 더 간소화할 수 있다. 중첩 함수를 사용하지 않고 주어진 함수를 그대로 호출해서 사용했다. 

if root:
    root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
    return root
return None

 

 

📌BFS

 

위에서는 leaf 노드부터 좌우 반전을 시작해야 한다고 적었지만 교재를 보니 BFS를 사용해서도 좌우 반전을 할 수 있었다. 

BFS의 경우 재귀함수로 구현이 불가능하므로 큐를 선언한 뒤 while문을 사용해서 큐의 앞에서 원소를 빼내고, 그 아래 레벨의 노드를 다시 큐의 맨 뒤에 넣으면서 구현했다. 

 

DFS는 leaf 노드부터 탐색이 진행되지만 BFS에서는 root 노드부터 시작해서 아래로 내려가면서 노드를 바꾼다. 

전체 코드는 다음과 같다. 

class Solution(object):

    def invertTree(self, root):
        queue = collections.deque([root])

        while queue:
            current = queue.popleft()
            if current:
                current.left, current.right = current.right, current.left
                queue.append(current.left)
                queue.append(current.right)

        return root

 

 

📌DFS

 

위의 코드에서 한 줄만 바꾸면 BFS 대신 DFS로 구현할 수 있다고 한다. 

BFS는 FIFO인 큐를 사용하는 반면 DFS는 LIFO인 스택을 사용하므로, 큐의 맨 앞에서부터 노드를 빼내던 로직을 큐의 맨 뒤에서부터 노드를 제거하도록 수정하면 된다. 

 

참고한 포스트

https://velog.io/@hysong/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%8B%A4%EC%A4%91-%ED%95%A0%EB%8B%B9Multiple-Assignment