Дерево двоичного поиска Python: упражнение 3 с решением
Напишите программу на Python, чтобы проверить, является ли данное двоичное дерево допустимым деревом двоичного поиска (BST) или нет.
Пусть двоичное дерево поиска (BST) определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами меньше ключа узла.
Правое поддерево узла содержит только узлы с ключами, превышающими ключ узла.
И левое, и правое поддеревья также должны быть двоичными деревьями поиска.
Пример 1: 2/ 1 3 Двоичное дерево [2,1,3], вернуть истину. Пример 2: 1/ 2 3Двоичное дерево [1,2,3], вернуть ложь.
Пример решения :
Код Python:
класс TreeNode (объект): def __init __ (self, x) : self.val = x self.left = None self.right = Nonedef is_BST (root): stack = [] prev = None while root или stack: while root: stack.append (root) root = root.left root = stack .pop () if prev и root.val
Пример вывода:
TrueFalse
Блок-схема:
Редактор кода Python:
