kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_8_A: Binary Search Tree I (続きの続き)

もっとがんばって関数型っぽい雰囲気を目指すとどうなるのか
といっても入出力ありで関数型っぽく書くっていうのがどういうことなのか
よくわかっていなかったりする
Scheme手習いとかでは入力は引数だけ、出力は値だけだったからなあ

とりあえず入出力はできるだけ狭い範囲に閉じ込めた
命令を順次処理しながら木を作っていくところでreduceを使ったのは
どうなんだろう
若干無理をしてる気がしないでもないけど

from sys import stdin
from functools import reduce

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

def insert(tree, z):
    if tree is None:
        return z
    elif z.key < tree.key:
        return Node(tree.key,
                    insert(tree.left, z),
                    tree.right)
    else:
        return Node(tree.key,
                    tree.left,
                    insert(tree.right, z))

def flatten_inorder(tree):
    if tree is None:
        return []
    else:
        return flatten_inorder(tree.left) + \
            [tree.key] + \
            flatten_inorder(tree.right)

def flatten_preorder(tree):
    if tree is None:
        return []
    else:
        return [tree.key] + \
            flatten_preorder(tree.left) + \
            flatten_preorder(tree.right)

def process_command(tree, command):
    if command[0] == "insert":
        return insert(tree, Node(int(command[1])))
    elif command[0] == "print":
        print("", *flatten_inorder(tree))
        print("", *flatten_preorder(tree))
        return tree

def main():
    _ = int(stdin.readline())

    reduce(process_command,
           [line.split() for line in stdin],
           None)

main()

とうぜんデータ数が多いとTLEです