Проверить бинарное дерево поиска

Question

Учитывая двоичное дерево, определите, является ли оно действительным двоичным деревом поиска (BST).

Предположим, что BST определено следующим образом:

Левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами, которые больше ключа узла. Левое и правое поддеревья также должны быть деревьями двоичного поиска.

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true
Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Мой код:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:



        def helper(node, lower = float('-inf'), upper = float('inf')):
            if(not node):
                return True

            if(node.val<=lower or node.val>=upper):
                return False
            if not helper(node.right, node.val, upper):
                return False
            if not helper(node.left, lower, node.val):
                return False
            return True


        return helper(root)

Приведенный выше код хорошо работает для всех тестовых случаев. Однако приведенный ниже код этого не делает.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:



        def helper(node, lower = float('-inf'), upper = float('inf')):
            if(not node):
                return True

            if(node.val<=lower or node.val>=upper):
                return False
            helper(node.right, node.val, upper)
            helper(node.left, lower, node.val)
            return True


        return helper(root)

Зачем нужны дополнительные условия IF? Даже без них функции должны возвращать false из условия if справа внизу? Что мне здесь не хватает?

 if(node.val<=lower or node.val>=upper):
                    return False

Answer 1

Вы в основном спрашиваете, в чем разница:

if not helper(node.right, node.val, upper):
    return False
if not helper(node.left, lower, node.val):
    return False
return True

и:

helper(node.right, node.val, upper)
helper(node.left, lower, node.val)
return True

Первый проверяет возвращаемое значение из вызовов helper и действует соответствующим образом, возвращает false, если поддерево не BST. Вторая проверяет поддеревья, а затем возвращает true независимо от того, что.

---

Это важно. Определение действительного BST состоит в том, что root больше root.left и меньше root.right, и что root.left и root.right являются также действительными BST.

При игнорировании этих возвращаемых значений единственное, что вы проверяете, это то, что три верхних узла имеют действительный BST. Другими словами, это пройдет, несмотря на то, что около действительно:

    __4__
   /     \
  2       8
 / \     / \
3   1   9   7

---

Без возврата результата на каждый уровень рекурсии, вы в основном теряете it.

Рассмотрим приведенный ниже код, который похож на вопрос, который вы подняли в комментарии («Но внутри вспомогательной функции есть условие if, которое возвращает false right? Как это не вступает в игру?»). ? "):

def level2():
    return 42          # Returns '42'.

def level1():
    level2()           # Returns 'None', not '42'.

print(level1())        # Prints 'None'.

Это печатает None, поскольку, даже если вы возвращаете 42 на втором уровне, оно выбрасывается на первом уровне.

Правильный метод изменит level2() позвоните в return level2().

---

В качестве отступления, я не уверен, какое значение вы получаете от upper и lower здесь.

Рекурсивное определение действительности означает, что only , что вам нужно проверить, - это три непосредственных узла и поддеревья.

Другими словами, этого будет достаточно (псевдокод, даже если он выглядит как Python, последний является идеальной базой строка для первого):

def isValidBst(node):
    # Empty tree is valid (or sub-tree, for that matter
    # but, since we never descend into a null, that's a
    # moot point).

    if node is null: return true

    # Check left value and sub-tree.

    if node.left is not null:
        if node.left.value >= node.value: return false
        if not isValidBst(node.left): return false

    # Check left value and sub-tree.

    if node.right is not null:
        if node.right.value <= node.value: return false
        if not isValidBst(node.right): return false

    # If there were no failures, including the possibility
    # we're at a leaf node, everything below this node is
    # okay.

    return true