如何判斷是否為標準二元搜索數(shù)（binarysearchtree）？-創(chuàng)新互聯(lián)

問題描述

創(chuàng)新互聯(lián)公司不只是一家網(wǎng)站建設的網(wǎng)絡公司；我們對營銷、技術、服務都有自己獨特見解，公司采取“創(chuàng)意+綜合+營銷”一體化的方式為您提供更專業(yè)的服務！我們經(jīng)歷的每一步也許不一定是最完美的，但每一步都有值得深思的意義。我們珍視每一份信任，關注我們的成都網(wǎng)站設計、成都網(wǎng)站制作質量和服務品質，在得到用戶滿意的同時，也能得到同行業(yè)的專業(yè)認可，能夠為行業(yè)創(chuàng)新發(fā)展助力。未來將繼續(xù)專注于技術創(chuàng)新，服務升級，滿足企業(yè)一站式全網(wǎng)營銷推廣需求，讓再小的品牌網(wǎng)站建設也能產生價值！

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

環(huán)境：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()

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標題：如何判斷是否為標準二元搜索數(shù)（binarysearchtree）？-創(chuàng)新互聯(lián)
本文URL：http://bm7419.com/article44/djphhe.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護、微信小程序、品牌網(wǎng)站設計、網(wǎng)頁設計公司、面包屑導航、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)