如何判断是否为标准二元搜索数（binarysearchtree）？-创新互联

问题描述

创新互联公司不只是一家网站建设的网络公司；我们对营销、技术、服务都有自己独特见解，公司采取“创意+综合+营销”一体化的方式为您提供更专业的服务！我们经历的每一步也许不一定是最完美的，但每一步都有值得深思的意义。我们珍视每一份信任，关注我们的成都网站设计、成都网站制作质量和服务品质，在得到用户满意的同时，也能得到同行业的专业认可，能够为行业创新发展助力。未来将继续专注于技术创新，服务升级，满足企业一站式全网营销推广需求，让再小的品牌网站建设也能产生价值！

In this problem you are going to test whether a binary search tree data structure from some programming language library was implemented correctly. There is already a program that plays with this data structure by inserting, removing, searching integers in the data structure and outputs the state of the internal binary tree after each operation. Now you need to test whether the given binary tree is indeed a correct binary search tree. In other words, you want to ensure that you can search for integers in this binary tree using binary search through the tree, and you will always get correct result: if the integer is in the tree, you will find it, otherwise you will not.

任务. You are given a binary tree with integers as its keys. You need to test whether it is a correct binary search tree. The definition of the binary search tree is the following: for any node of the tree, if its key is 𝑥, then for any node in its left subtree its key must be strictly less than 𝑥, and for any node in its right subtree its key must be strictly greater than 𝑥. In other words, smaller elements are to the left, and bigger elements are to the right. You need to check whether the given binary tree structure satisfies this condition. You are guaranteed that the input contains a valid binary tree. That is, it is a tree, and each node has at most two children.

输入. The first line contains the number of vertices 𝑛. The vertices of the tree are numbered from 0 to 𝑛 − 1. Vertex 0 is the root. The next 𝑛 lines contain information about vertices 0, 1, ..., 𝑛−1 in order. Each of these lines contains three integers 𝑘𝑒𝑦𝑖 , 𝑙𝑒𝑓 𝑡𝑖 and 𝑟𝑖𝑔ℎ𝑡𝑖 — 𝑘𝑒𝑦𝑖 is the key of the 𝑖-th vertex, 𝑙𝑒𝑓 𝑡𝑖 is the index of the left child of the 𝑖-th vertex, and 𝑟𝑖𝑔ℎ𝑡𝑖 is the index of the right child of the 𝑖-th vertex. If 𝑖 doesn’t have left or right child (or both), the corresponding 𝑙𝑒𝑓 𝑡𝑖 or 𝑟𝑖𝑔ℎ𝑡𝑖 (or both) will be equal to −1. Constraints. 0 ≤ 𝑛 ≤ 10^5 ; −2^31< 𝑘𝑒𝑦𝑖< 2^31 − 1; −1 ≤ 𝑙𝑒𝑓 𝑡𝑖 , 𝑟𝑖𝑔ℎ𝑡𝑖 ≤ 𝑛 − 1. It is guaranteed that the input represents a valid binary tree. In particular, if 𝑙𝑒𝑓 𝑡𝑖 ̸= −1 and 𝑟𝑖𝑔ℎ𝑡𝑖 ̸= −1, then 𝑙𝑒𝑓 𝑡𝑖 ̸= 𝑟𝑖𝑔ℎ𝑡𝑖 . Also, a vertex cannot be a child of two different vertices. Also, each vertex is a descendant of the root vertex. All keys in the input will be different.

输出. If the given binary tree is a correct binary search tree (see the definition in the problem description), output one word “CORRECT” (without quotes). Otherwise, output one word “INCORRECT” (without quotes).

环境：python 3.10

解法：

import sys, threading

sys.setrecursionlimit(10 ** 7)  # max depth of recursion
threading.stack_size(2 ** 27)  # new thread will get stack of such size
mini = -(2 ** 64)
maxi = 2 ** 64


def isbit(i, mini, maxi):
    #main algorithm
    if i == -1:
        return True
    le = left[i]
    ri = right[i]
    if le != -1 and (node[le] >node[i] or node[le]< mini):
        return False
    if ri != -1 and (node[ri]< node[i] or node[ri] >maxi):
        return False

    return (isbit(le, mini, node[i] - 1) and
            isbit(ri, node[i] + 1, maxi))

def isbinarysearchtree(i):

    return isbit(i, mini, maxi)

def leftbiggerroot(root):
    #search if there are some outrange descendants in the left area
    if root == -1:
        return True
    no = node[root]
    if no >node[0] :
        return False
    return (leftbiggerroot(right[root]) and
            leftbiggerroot(left[root]))

def rightsmallerroot(root):
    #search if there are some outrange descendants in the right area
    if root == -1:
        return True
    no = node[root]
    if no< node[0]:
        return False
    return (rightsmallerroot(left[root]) and
            rightsmallerroot(right[root]))

def main():
    #initialization   
    nodes = int(sys.stdin.readline().strip())
    if nodes == 0:
        print("CORRECT")
        return 0
    global node
    node = [0] * nodes
    global left
    left = [0] * nodes
    global right
    right = [0] * nodes

    for i in range(nodes):
        line = sys.stdin.readline().strip().split()
        node[i] = int(line[0])
        left[i] = int(line[1])
        right[i] = int(line[2])

    if (isbinarysearchtree(0) and leftbiggerroot(left[0]) and                                 
        rightsmallerroot(right[0])):
        print("CORRECT")
    else:
        print("INCORRECT")


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

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：如何判断是否为标准二元搜索数（binarysearchtree）？-创新互联
文章路径：http://cqcxhl.com/article/djphhe.html