[알고리즘] 이진 트리 반전

이진 트리 반전

책 풀이 1

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root:
            root.left , root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root
        return None

self.invertTree(root.right)가 먼저 실행되고, 그 다음 self.invertTree(root.left)가 실행된다.

가장 오른쪽인 노드 9로 가서 바꾼뒤 그 다음 6노드도 하위 노드들을 바꾼다. 그 다음 7노드 왼쪽 오른쪽을 바꾸는 방식이다.

책 풀이 2

class Solution:
   def invertTree(self, root: TreeNode) -> TreeNode:
       queue = collections.deque([root])
       
       while queue:
           node = queue.popleft()
           if node:
               node.left, node.right = node.right, node.left
               
               queue.append(node.left)
               queue.append(node.right)

top-down 방식이다.