[Python][LeetCode] Invert Tree

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

Invert Binary Tree - LeetCode

문제 설명

주어진 리스트를 트리로 바꿔 왼쪽과 오른쪽이 바뀐 값을 출력하면 된다.

 

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

트리를 만드는 노드를 만들어준다. 노드는 왼쪽과 오른쪽을 가지고 있다.

 

def make_tree(lst, idx):
    parent = None
    if idx < len(lst):
        value = lst[idx]
        if value == None:
            return

        parent = TreeNode(value)
        parent.left = make_tree(lst, 2 * idx + 1)
        parent.right = make_tree(lst, 2 * idx + 2)

    return parent

트리를 만들어주는 함수이다.

가장 루트노드를 만들고 인덱스를 증가시켜 left와 right을 만든다.

 

def invertTree(lst):

    root = make_tree(lst, 0)
    queue = 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)

    return lst

루트부터 트리에 접근한다.

left와 right을 꺼내 두 값을 바꿔 큐에 넣어준다.