时间戳

首页 > 解决方案 > 验证具有重复键的二叉搜索树

python - 验证具有重复键的二叉搜索树

问题描述

给定一个以整数作为键的二叉树，我需要测试它是否是正确的二叉搜索树。允许重复整数。较小的元素在左边，较大的元素在右边，重复的元素总是在右边

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 的信息。这些行中的每一行都包含三个整数 key，left 和 right

输出格式。如果给定的二叉树是正确的二叉搜索树，则输出一个单词“CORRECT”。否则，输出一个单词“INCORRECT”。

例子：

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

我正在一场编程比赛中解决这个任务。而且我未能满足所有测试用例。似乎我在某个地方弄错了。但是我找不到被错误标记的测试用例。

如果你提出我的错误，我将不胜感激

标签： pythonalgorithmbinary-search-tree

解决方案

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

推荐阅读