[99클럽 코테 스터디] 3일차 TIL - 깊이/너비 우선 탐색(DFS/BFS), Invert Binary Tree

[3일차] 깊이/너비 우선 탐색(DFS/BFS)

 

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

My Solution

* Runtime: 17ms

문제가 제시한 예시 2처럼 깊이가 2인 트리를 반전하는 동작을 반복하여 전체 트리를 반전시킬 수 있다.

즉, '깊이가 2인 트리를 반전하는 동작'을 재귀함수로 정의해보자.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """

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

        return root

Better Solution

* Runtime: 7ms

나의 코드와 같지만, 교환에서 재귀를 호출하지 않았다는 점이 다르다.

class Solution(object):
    def invertTree(self, root):
        if not root: return
        root.right, root.left = root.left, root.right
        root.left = self.invertTree(root.left)
        root.right = self.invertTree(root.right)
        return root

* Runtime: 0ms

재귀 호출을 튜플 대입 방식으로 활용한 나의 코드와 다르게 더 빠른 실행 속도를 내는 정답 코드이다. 

교환을 수행하기 전 원본을 저장해야 하기 때문에 left 변수를 사용했다.

class Solution(object):
    def invertTree(self, root):
        if root:
            left = root.left
            root.left = self.invertTree(root.right)
            root.right = self.invertTree(left)
        return root

나의 코드에서는 두 번(왼+오)의 재귀 호출이 동시에 일어난다. 두 개의 재귀 호출이 완료된 후에야 root.left와 root.right가 교환되어 메모리 접근 패턴이 다소 복잡해진다. 스택 호출에 더 많은 깊이가 필요한 것이다.

모범 코드에서는 root.left를 left에 저장하고, 두 자식을 각각 반전시킨다. 한 번에 하나씩 단계적으로 재귀 호출이 일어나, 호출 스택에서 하나의 호출이 완료된 후에야 다른 호출이 시작된다.

나다어

• 한 뭉치의 반복 작업은 재귀를 활용한다.
  이 때, 깔끔하게 한 뭉치를 정의하는 것이 핵심이고 그 뭉치가 곧 재귀함수가 된다. 재귀를 활용하지 않은 기본 코드를 먼저 짜보고, 어느 부분에 재귀를 넣을 수 있는지 고민하면 빠르다.
• 성능 최적화를 고민하자.