Problem :

https://www.hackerrank.com/challenges/swap-nodes-algo/problem


My Solution :

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(2000)
from collections import deque


class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None
        self.depth = 1


class Tree(object):
    def __init__(self):
        self.root = Node(1)

    def create_tree(self, data):
        queue = deque()
        data.reverse()
        queue.append(self.root)
        while queue:
            node = queue.popleft()
            left, right = data.pop()
            if left != -1:
                node.left = Node(left)
                node.left.depth = node.depth + 1
                queue.append(node.left)
            if right != -1:
                node.right = Node(right)
                node.right.depth = node.depth + 1
                queue.append(node.right)

    def swap_node(self, k):
        queue = deque()
        queue.append(self.root)
        while queue:
            node = queue.popleft()
            if node.depth % k == 0:
                node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    def in_order_traverse(self, node, result):
        if node:
            self.in_order_traverse(node.left, result)
            result.append(node.data)
            self.in_order_traverse(node.right, result)
        return result


def swapNodes(indexes, queries):
    tree = Tree()
    tree.create_tree(indexes)
    for k in queries:
        tree.swap_node(k)
        result = tree.in_order_traverse(tree.root, [])
        print(' '.join(map(str, result)))


n = int(input())
indexes = []
for _ in range(n):
    indexes.append(list(map(int, input().rstrip().split())))
queries_count = int(input())
queries = []
for _ in range(queries_count):
    queries_item = int(input())
    queries.append(queries_item)
swapNodes(indexes, queries)


Comment :

파이썬 기본 recursion limit 값이 1000인데, 일부 testcase는 1000 이상의 recursion을 수행하여 timeout 발생한다. 따라서 sys 모듈을 import 해서 sys.setrecursionlimit() 함수로 값을 늘려줘야 한다.