Преобразование отсортированного массива в сбалансированное двоичное дерево поиска (BST) — распространенная проблема на собеседованиях по информатике и программированию. Этот процесс включает в себя перестановку элементов массива для создания двоичного дерева, которое сохраняет отсортированный порядок исходного массива, обеспечивая при этом максимально сбалансированное дерево. В этой статье мы рассмотрим несколько методов выполнения этой задачи, предоставляя попутно разговорные объяснения и примеры кода.

Метод 1: рекурсивный подход

Один из наиболее интуитивно понятных методов преобразования отсортированного массива в сбалансированный BST — использование рекурсивного подхода. Основная идея состоит в том, чтобы найти средний элемент массива и сделать его корнем BST. Затем рекурсивно повторите процесс для левой и правой половин массива, чтобы построить левое и правое поддеревья.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def sortedArrayToBST(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid + 1:])
    return root

Метод 2: итеративный подход со стеками

Другой подход предполагает использование итерационного алгоритма со стеками для преобразования отсортированного массива в сбалансированный BST. Этот метод позволяет избежать рекурсии и использует стек для отслеживания узлов, которые необходимо обработать.

def sortedArrayToBST(nums):
    if not nums:
        return None
    stack = []
    left_boundaries = []
    right_boundaries = []
    root = TreeNode()
    stack.append((0, len(nums) - 1, root, True))
    while stack:
        left, right, node, is_left = stack.pop()
        mid = (left + right) // 2
        node.val = nums[mid]
        if is_left:
            left_boundaries.append((left, mid - 1, node))
        else:
            right_boundaries.append((mid + 1, right, node))
        if left <= mid - 1:
            stack.append((left, mid - 1, node.left, True))
        if mid + 1 <= right:
            stack.append((mid + 1, right, node.right, False))
    for left, right, parent in left_boundaries:
        parent.left = TreeNode()
        stack.append((left, right, parent.left, True))
    for left, right, parent in right_boundaries:
        parent.right = TreeNode()
        stack.append((left, right, parent.right, False))
    return root

Метод 3: обход по порядку с построением массива

Другой подход предполагает выполнение обхода BST по порядку и постепенное построение дерева. Этот метод использует вспомогательную функцию, которая принимает левую и правую границы массива в качестве параметров и строит дерево путем рекурсивного деления массива.

def sortedArrayToBST(nums):
    def constructTree(left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        node.left = constructTree(left, mid - 1)
        node.right = constructTree(mid + 1, right)
        return node
    return constructTree(0, len(nums) - 1)

В этой статье мы рассмотрели три различных метода преобразования отсортированного массива в сбалансированный BST. Рекурсивный подход, итеративный подход со стеками и обход по порядку с построением массива — все они обеспечивают эффективные решения этой проблемы. В зависимости от конкретных требований и ограничений вашего проекта вы можете выбрать наиболее подходящий метод. Поняв эти методы, вы будете хорошо подготовлены к решению подобных задач и продемонстрируете свои навыки программирования на собеседованиях.