BST (дерево двоичного поиска) Testdome в Python - PullRequest
Новая
       19

BST (дерево двоичного поиска) Testdome в Python

0 голосов
/ 27 февраля 2020

Мне нужно решение проблемы, которое выложено в тест-куполе.

Вот проблема

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

Напишите функцию, которая эффективно с точки зрения используемого времени проверяет, содержит ли данное двоичное дерево поиска заданное значение.

Для Например, для следующего дерева:

n1 (значение: 1, слева: ноль, справа: ноль) n2 (значение: 2, слева: n1, справа: n3) n3 (значение: 3, слева: ноль , Справа: null) При вызове содержимого (n2, 3) должно быть возвращено значение True, поскольку дерево с root в n2 содержит число 3.

И вот мой ответ. Я программирую python. 

import collections
Node = collections.namedtuple('Node', ['left', 'right', 'value'])

def contains(root, value):
    if value == root.value:
        return True
    elif value > root.value:
        if root.right != None:
            return contains(root.right, value)
    elif value < root.value:
        if root.left != None:
            return contains(root.right, value)


n1 = Node(value=1, left=None, right=None)
n3 = Node(value=3, left=None, right=None)
n2 = Node(value=2, left=n1, right=n3)

print(contains(n2, 2))

Теперь я прошел 33,3%, Пожалуйста, помогите мне пройти 100%

Ответы [ 2 ]

0 голосов
/ 27 февраля 2020

Вам нужно сначала проверить, если root равно None, затем вернуть False, вам не нужно проверять, если root.left is None или root.right is None

Затем, как и другой упомянутый ответ , ваш код всегда выглядит правильно.

Если искомое значение меньше, чем значение root go влево.

Также вам не нужно elif, потому что вы возвращаетесь из if

С такими изменениями: 

def contains(root, value):
    if root is None:
        return False
    if value == root.value:
        return True
    if value > root.value:
        return contains(root.right, value)
    if value < root.value:
        return contains(root.left, value)
0 голосов
/ 27 февраля 2020

точка 1: вы идете по правильному поддереву всегда. значение root ниже или выше, чем у ключа.

точка 2: вы должны go уйти, когда значение root выше, чем у ключа.

точка 3: вы должны go вправо, когда значение root ниже, чем ключ.

сделать следующие изменения в вашем коде: 

if value == root.value:
    return True
elif root.value > value:
    if root.left != None:
        return contains(root.left, value) #going left
elif root.value < value:
    if root.right != None:
         return contains(root.right, value) #going right
...