Assignment 4 - Is it binary trees?

Assignment 4 - Is it binary trees?

이번 과제는 binary tree 특성 여부를 알아내는 문제이다.

여기서 해결해야 할 것은 binary search tree의 중요 특성 중 하나인 각 노드의 키값이 왼쪽의 모든 자식노드보다 크고 오른쪽의 모든 자식노드보다 작으면 되는 특성을 만족시켜야 한다.

첫번째 샘플을 보면 3개의 노드가 특성에 맞게 자리잡혀 있는 걸 알 수 있고 2번째 샘플은 자리만 바뀌었는데 특성이 불만족하는 것을 볼 수 있다. 3번째 샘플에서 알 수 있듯 트리가 없을 때는 만족하는 것으로 출력한다.

4번째 샘플과 5번째 샘플은 좀 더 복잡한 구성이지만 결국 특성을 만족하여 CORRECT라는 출력을 내보낸다.

6번째 샘플은 루트의 왼쪽 자식노드 중 하나인 5가 루트인 4보다 크기에 조건을 만족하지 않는다.

#!/usr/bin/python3
import sys, threading

sys.setrecursionlimit(10**7) # max depth of recursionthreading.stack_size(2**25)  # new thread will get stack of such size
def IsBinarySearchTree(tree):
  # Implement correct algorithm here  return True

def main():
  nodes = int(sys.stdin.readline().strip())
  tree = []
  for i in range(nodes):
    tree.append(list(map(int, sys.stdin.readline().strip().split())))
  if IsBinarySearchTree(tree):
    print("CORRECT")
  else:
    print("INCORRECT")

threading.Thread(target=main).start()

코드 기본 틀이며 위의 IsBinarySearchTree의 구성을 완성시키면 된다.

#!/usr/bin/python3
import sys, threading

sys.setrecursionlimit(10**7) # max depth of recursionthreading.stack_size(2**25)  # new thread will get stack of such size

def IsBinarySearchTree(tree):
    # Implement correct algorithm here    if not tree:
        return True    else:
        root = tree[0]

    def _isBST(root, left=None, right=None):
        if root is None:
            return True        if left is not None and root[0] < left[0]:
            return False        if right is not None and root[0] > right[0]:
            return False
        if root[1] == -1 and root[2] == -1:
            return True        elif root[1] == -1 and root[2] != -1:
            return _isBST(tree[root[2]], root, right)
        elif root[1] != -1 and root[2] == -1:
            return _isBST(tree[root[1]], left, root)
        else:
            return _isBST(tree[root[1]], left, root) and _isBST(tree[root[2]], root, right)
    return _isBST(root, None, None)


def main():
    nodes = int(sys.stdin.readline().strip())
    tree = []
    for i in range(nodes):
        tree.append(list(map(int, sys.stdin.readline().strip().split())))
    if IsBinarySearchTree(tree):
        print("CORRECT")
    else:
        print("INCORRECT")


threading.Thread(target=main).start()

위와 같이 IsBinarySearchTree의 하위에 _isBST 메쏘드를 두고 recursive 구성으로 짜보았다. 약간 꼬인감이 있지만 제대로 동작하며 대신 과제를 하면서 'unknown signal 11'이라는 에러메세지가 등장하였다. 2년전에도 해결을 못하고 수동으로 패스시켰다고하니 넘어가야겠다.

나머지 한문제를 더 맞춰야 하지만 시간관계상 구글의 도움을 받아 넘어가게 되었다. 빨리 객체지향언어로 넘어가야겠다.