Проверьте двоичное дерево поиска с дубликатами ключей - PullRequest
Новая
       10

Проверьте двоичное дерево поиска с дубликатами ключей

0 голосов
/ 01 декабря 2018

Учитывая двоичное дерево с целыми числами в качестве ключей, мне нужно проверить, является ли оно правильным двоичным деревом поиска.Допускается дублирование целых чисел.Меньшие элементы находятся слева, большие элементы - справа, а дубликаты всегда справа 

import sys, threading
def IsBinarySearchTree(tree):
  # Implement correct algorithm here
  min = -sys.maxsize
  max = sys.maxsize

  def is_bst_until(idx_node,maxi,mini, is_left = False):
    if idx_node == -1:
      return True

    node = tree[idx_node]
    key = node[0]
    idx_left = node[1]
    idx_right = node[2]    

    if (key>maxi) or (key<mini):
      return False

    if is_left:
      if (key==mini):
        return False

    return (is_bst_until(idx_right, maxi, key)) and (is_bst_until(idx_left, key-1, mini, is_left=True))

  if len(tree) == 0:
      return True
  return is_bst_until(0, max, min)


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()

Формат ввода.Первая строка содержит количество вершин n.Вершины дерева пронумерованы от 0 до n − 1.Вершина 0 является корнем.Следующие n строк содержат информацию о вершинах 0, 1, ..., ? - 1 по порядку.Каждая из этих строк содержит три целых клавиши, левый и правый

Формат вывода.Если данное двоичное дерево является правильным двоичным деревом поиска, выведите одно слово «ПРАВИЛЬНО».В противном случае выведите одно слово «НЕПРАВИЛЬНО».

Примеры: 

3
2 1 2
2 -1 -1
3 -1 -1
#Incorrect

5
1 -1 1
2 -1 2
3 -1 3
4 -1 4
5 -1 -1
#Correct

Я решаю эту задачу в одном соревновании по программированию.И мне не удалось выполнить все контрольные примеры.Кажется, я где-то ошибся.Однако я не смог найти контрольный пример с неправильной маркировкой.

Буду признателен, если вы предложите мне мою ошибку

1 Ответ

0 голосов
/ 01 декабря 2018 
import sys, threading
def IsBinarySearchTree(tree):
  # Implement correct algorithm here
  def is_bst_until(idx_node):
    if idx_node == -1:
      return True

    node = tree[idx_node]
    key = node[0]
    idx_left = node[1]
    idx_right = node[2]    

    if(idx_left != -1 and key <= tree[idx_left][0]):
        return False;

    if(idx_right != -1 and key > tree[idx_right][0]):
        return False;


    return (is_bst_until(idx_right)) and (is_bst_until(idx_left))

  if len(tree) == 0:
      return True
  return is_bst_until(0)


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()
...