[LeetCode][Python] 226. Invert Binary Tree

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

- 난이도: Easy

 

binary tree에서 모든 subtree의 left, right를 바꾸면 된다

재귀 호출하는 방법과, 큐를 쓰는 방법이 있다

 

(1) 재귀 호출하는 방법

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

 

(2) 큐 쓰는 방법

파이썬 list의 pop(0)은 모든 원소를 한칸씩 땡기기 때문에, deque를 썼다

# from collections import deque

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        d = deque()
        d.append(root)
        while d:
            cur = d.popleft()
            cur.left, cur.right = cur.right, cur.left

            if cur.left:
                d.append(cur.left)
            if cur.right:
                d.append(cur.right)

        return root