6.8

main.py

"""
# 문제 : 이진 트리 반전

트리의 루트를 기준으로 좌우 노드를 바꾸는 코드를 작성하라.

### 아이디어 (반복 - 스택)

1. 스택 생성
2. 루트 노드를 스택에 추가
3. 스택이 비어있을 때 까지
  - 노드를 방문
  - 왼쪽 / 오른쪽 노드를 교환
  - 스택에 왼쪽, 오른쪽 노드 추가

### 아이디어 (재귀 - 스택)
1. 노드가 None 이라면 반환
2. 노드의 왼쪽 오른쪽 노드를 교환
3. 왼쪽 노드로 재귀 호출
4. 오른쪽 노드로 재귀 호출

### 아이디어 (큐)

1. 큐를 생성
2. 루트를 큐에 추가
3. 큐가 비어있을 때까지
  - 현재 큐가 가지고 있는 모든 노드를 꺼낸다.
  - 꺼낸 노드의 왼쪽과 오른쪽 노드의 교환
  - 왼쪽과 오른쪽 노드를 큐에 추가한다.
  
"""
from collections import deque


class Node:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val


def invertTree(root: Node) -> Node:
    """
    스택을 이용한 방법
    :param root: 
    :return: 
    """
    if not root:
        return

    stack = [root]

    while len(stack):
        node = stack.pop()
        node.left, node.right = node.right, node.left

        if not node.left:
            stack.append(node.left)
        if not node.right:
            stack.append(node.right)
    return node


def invertTree(root: Node) -> Node:
    """
    재귀를 이용한 방법
    :param root: 
    :return: 
    """
    if not root:
        return

    # swap nodes
    root.left, root.right = root.right, root.left

    invertTree(root.left)
    invertTree(root.right)

    return root


def invertTree(root: Node) -> Node:
    """
    큐를 이용한 방법
    :param root: 
    :return: 
    """
    if not root:
        return
    
    queue = deque(root)
    
    while len(queue):
        cnt = len(queue)
        
        for _ in range(cnt):
            node = queue.popleft()
            
            node.left, node.right = node.right, node.left
            
            if not node.left:
                queue.append(node.left)
            if not node.right:
                queue.append(node.right)
        return node