Не удалось вставить значение в дерево двоичного поиска

Question

У меня возникли проблемы с функцией вставки BST.

Похоже, что после выполнения этого кода нет выходов, возвращаемых;Однако я не могу успешно вставить значение в дерево.

Точнее, пока я использовал Spyder для проверки, значение root равно NoneType object of bulitins module. В результате я почти уверен, что мне не удалось вставить значение в дерево. И я подозреваю, что это из-за NoneType корня, но даже если я попытался дать root значение до запуска кода с помощью root = TreeNode(3), то Solution().insert(root, 5). Я не уверен, как решить эту проблему.

Пожалуйста, посмотрите на следующий код.

class TreeNode():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution():    

    def insert(self, root, val):

        if root is None:
            root = TreeNode(val)
            return root
        else:
            if val <= root.val:
                if root.left:
                    root.left = self.insert(root.left, val)
            else:
                if root.right:
                    root.right = self.insert(root.right, val)
                return root


root = None
Solution().insert(root, 5)

Любое предложение будет высоко оценено !!

Answer 1

Существует ошибка (вам не нужно проверять if root.left: и if root.right:, потому что в рекурсивных вызовах вы обрабатывали условие none ) в вашем состоянии рекурсивных вызовов, а также операторы return, которые только в правесторона дерева не для левой стороны дерева, поэтому она не работает в соответствии с вашими ожиданиями:

def insert(self, root, val):

    if root is None:
        root = TreeNode(val)
        return root
    else:
        if val <= root.val:
            root.left = self.insert(root.left, val)
        else:
            root.right = self.insert(root.right, val)
        return root

Вот ссылка на рабочий код: ссылка