Python 알고리즘 인터뷰 - 문제 45. 이진 트리 반전

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

 

문제

주어진 이진트리를 반전 시켜라

예제1

입력 : root = [4, 2, 7, 1, 3, 6, 9]

출력 : [4, 7, 2, 9, 6, 3, 1]

 

예제2

입력 : root = [2, 1, 3]

출력 : [2, 3, 1]

 

예제3

입력 : root = []

출력 : []

 

풀이

노드의 좌, 우 노드를 swap하며 swap된 좌, 우 node를 재귀적으로 계속 swap호출하면 해결되는 문제이다. 다음 트리를 예로 설명해본다.

 

먼저 1과 연결된 2, 3 노드를 swap하면 다음과 같다.

 

이후 swap된 좌측 노드를 3을 기준으로 swap한다.

리프노드 7,6 는 swap할 자식 노드가 없으므로 pass한다.

이제 오른쪽에 2번 노드의 자식을 swap 하면 이진 트리 반전이 완료된다.

전체 구조로 보면 root 노드부터 자식 노드까지 각 swap이 재귀적으로 이뤄짐을 알 수 있다. 

이를 통해 코드를 구현하면 다음과 같다.

전체코드

class Solution:
    def invertTree(self, root):
        def invert(node):
            if not node:
                return

            node.left, node.right = node.right, node.left
            invert(node.left)
            invert(node.right)

        invert(root)
        return root