Проверка BST и свойств симметричного обхода

Задача проверки BST

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

# Why local check fails:
#     5
#    / \
#   1   4
#      / \
#     3   6
# Node 4's children (3, 6) satisfy local rule,
# but 4 < 5 and is in the RIGHT subtree -- BST violated!
print('Local check is insufficient -- use min/max bounds')

Подход с нижней и верхней границами

def is_valid_bst(root, low=float('-inf'), high=float('inf')):
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

# Valid BST:
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
print(is_valid_bst(valid))  # True

# Invalid BST (3 is in wrong subtree conceptually):
invalid = TreeNode(5)
invalid.left = TreeNode(1)
invalid.right = TreeNode(4)
invalid.right.left = TreeNode(3)
invalid.right.right = TreeNode(6)
print(is_valid_bst(invalid))  # False (4 < 5 in right subtree)

Проверка с помощью симметричного обхода

def is_valid_bst_inorder(root):
    prev = [float('-inf')]

    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:  # not strictly increasing
            return False
        prev[0] = node.val
        return inorder(node.right)

    return inorder(root)

valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
valid.left.left = TreeNode(1)
valid.left.right = TreeNode(4)
print(is_valid_bst_inorder(valid))   # True

invalid = TreeNode(5)
invalid.left = TreeNode(6)  # 6 > 5 in left subtree!
print(is_valid_bst_inorder(invalid)) # False

Сравнение обоих подходов к проверке

# Both approaches:
# Time: O(n) -- visit each node once
# Space: O(h) -- call stack depth
# h = O(log n) balanced, O(n) skewed

# When to choose which:
# min/max bounds:
#   - Cleaner for trees with constraints beyond BST
#   - No global state (purely functional)
# in-order prev:
#   - More intuitive (sorted sequence check)
#   - Easier to convert to iterative with a stack

print('Both O(n) time, O(h) space -- choose by clarity')

Восстановление BST: два переставленных узла

def recover_tree(root):
    first = second = prev = None

    def inorder(node):
        nonlocal first, second, prev
        if not node:
            return
        inorder(node.left)
        if prev and prev.val > node.val:
            if not first:
                first = prev    # first violator
            second = node       # always update second
        prev = node
        inorder(node.right)

    inorder(root)
    # Swap values of the two misplaced nodes
    if first and second:
        first.val, second.val = second.val, first.val

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(2)  # 2 and 3 are swapped
recover_tree(root)
print(root.val, root.right.left.val)  # 2, 3 (fixed)

Преобразование BST в отсортированный массив с помощью симметричного обхода

def bst_to_sorted_array(root):
    result = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)
    inorder(root)
    return result

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print(bst_to_sorted_array(root))  # [1, 2, 3, 4, 5, 6, 7]

Объединение двух BST

def merge_two_bsts(root1, root2):
    def inorder(node, arr):
        if not node:
            return
        inorder(node.left, arr)
        arr.append(node.val)
        inorder(node.right, arr)

    arr1, arr2 = [], []
    inorder(root1, arr1)
    inorder(root2, arr2)

    # Merge two sorted arrays
    merged = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            merged.append(arr1[i]); i += 1
        else:
            merged.append(arr2[j]); j += 1
    merged.extend(arr1[i:])
    merged.extend(arr2[j:])
    return merged

r1 = TreeNode(2); r1.left = TreeNode(1); r1.right = TreeNode(4)
r2 = TreeNode(3); r2.left = TreeNode(0); r2.right = TreeNode(5)
print(merge_two_bsts(r1, r2))  # [0, 1, 2, 3, 4, 5]

Подсчёт узлов BST в диапазоне

def range_sum_bst(root, low, high):
    if not root:
        return 0
    total = 0
    if low <= root.val <= high:
        total += root.val
    if root.val > low:   # left subtree may have values >= low
        total += range_sum_bst(root.left, low, high)
    if root.val < high:  # right subtree may have values <= high
        total += range_sum_bst(root.right, low, high)
    return total

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15))  # 7 + 10 + 15 = 32

Повторяющиеся значения и строгий и нестрогий BST

# Strict BST (LeetCode default): left < root < right
def is_valid_strict(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    if not (lo < root.val < hi):  # STRICT inequalities
        return False
    return (is_valid_strict(root.left, lo, root.val) and
            is_valid_strict(root.right, root.val, hi))

# Non-strict BST (allows duplicates in right): left <= root < right
def is_valid_nonstrict(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    if not (lo <= root.val < hi):  # NOTE: <= for left side
        return False
    return (is_valid_nonstrict(root.left, lo, root.val + 1) and
            is_valid_nonstrict(root.right, root.val, hi))

print('Always clarify strict vs non-strict with interviewer')

Симметричный обход как универсальный инструмент для BST

# Problems solved elegantly with in-order:
# 1. Validate BST: check prev <= curr during in-order
# 2. Kth smallest: count k steps in in-order
# 3. Kth largest: count k steps in REVERSE in-order
# 4. Closest value to target: find crossover in in-order
# 5. BST to sorted array: collect in-order into list
# 6. Recover BST: find 1-2 violations in in-order
# 7. Sum of range [lo, hi]: accumulate during in-order

# The key insight: in-order visits BST nodes in sorted order.
# All sorted-order reasoning translates to in-order DFS.
print('In-order = sorted access = foundation of BST reasoning')

Ближайшее значение в BST

def closest_value(root, target):
    closest = root.val
    curr = root
    while curr:
        if abs(curr.val - target) < abs(closest - target):
            closest = curr.val
        if target < curr.val:
            curr = curr.left
        elif target > curr.val:
            curr = curr.right
        else:
            break  # exact match
    return closest

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_value(root, 3.714286))  # 4

Быстрая проверка

Итоги урока