LINUX.ORG.RU

задачка о binary search tree / часть тестов провалено

 , ,


0

1

Given the root node of a binary tree, can you determine if it's also a binary search tree?
You are not responsible for reading any input from stdin.
Hidden code stubs will assemble a binary tree and pass its root node to your function as an argument.Constraints: 0<=data<=10000

Моя функция проходит лишь 8 тестов из 14. Где здесь изъян?

def check_binary_search_tree_(root):
    if root.left or root.right: lst=[root]
    else: return 1

    while lst:
        new_list=[]
        for node in lst:
            if node.left:
                if node.data>node.left.data: new_list.append(node.left)
                else: return 0
            if node.right:
                if node.data<node.right.data: new_list.append(node.right)
                else: return 0
        lst=new_list
    return 1

ты бы скинул пример бинарного дерева и чем тестишь. тут даже не написано какое ты биинарное дерево используешь (но оно должно быть отсортированным, а значит каким-нибудь красно-черным)

tz4678 ()
class Node:
    def __init__(self, data, left, right):
        self.data = data
        self.left = left
        self.right = right

root = Node(5, Node(2, None, Node(25, None, None)), None)

print(check_binary_search_tree_(root))

Выведет 1, а не должно.

xaizek ★★★★★ ()
Ответ на: комментарий от Sorcerer

без разницы, как обходить дерево. Обход в глубину проще писать, на обходе в ширину нет риска получить ошибку из-за кучи рекурсивных вызовов

anonymous ()
Ответ на: комментарий от Sorcerer

Здрасьте, приехали. Если нам надо много говна в дерево пихать, то рекурсия такая сладкая на стеке. То что на нем рекурсию показывают студентам вовсе не означает что если ты серьезное дерево пишешь (которое реально где-то используется) то ты должен рекурсию использовать.

peregrine ★★★★★ ()