Преобразование отсортированного массива целых чисел в сбалансированное бинарное дерево: Решение задачи на LeetCode
В этой статье мы рассмотрим задачу с LeetCode, связанную с преобразованием отсортированного массива целых чисел в сбалансированное бинарное дерево поиска. Задача часто встречается в интервью на позиции программиста и является прекрасным способом познакомиться с принципами построения деревьев и рекурсивных алгоритмов.
Задача:
Given an array where elements are sorted in ascending order, convert it to a height-balanced binary search tree (BST).
Дан массив, в котором элементы упорядочены по возрастанию. Преобразуйте его в сбалансированное бинарное дерево поиска (BST).
Решение:
1. Понимание задачи:
Перед тем как начать кодировать, важно понять, что такое сбалансированное бинарное дерево и как его построить. Сбалансированное бинарное дерево - это дерево, в котором высоты двух поддеревьев любого узла различаются не более чем на 1.
2. Алгоритм:
- Мы будем использовать рекурсивный метод для построения дерева.
- На каждом шаге выбираем центральный элемент массива как значение корневого узла.
- Рекурсивно повторяем этот процесс для левого и правого подмассивов, чтобы построить левое и правое поддеревья.
3. Кодирование:
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return insertCentralElement(nums, 0, nums.length - 1);
}
private TreeNode insertCentralElement(int[] nums, int start, int end) {
// Базовый случай: массив состоит из одного элемента
if (start > end) {
return null;
}
// Рекурсивный случай: разбиваем массив на две части и рекурсивно вызываем функцию
int mid = (start + end) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = insertCentralElement(nums, start, mid - 1);
root.right = insertCentralElement(nums, mid + 1, end);
return root;
}
}
4. Тестирование:
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3, 4, 5, 6, 7};
TreeNode root = solution.sortedArrayToBST(nums);
// Выводим дерево в порядке inorder для проверки
System.out.println("Inorder traversal:");
solution.inorder(root);
}
private void inorder(TreeNode root) {
if (root != null) {
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
}
Заключение:
Решение задачи "Преобразование отсортированного массива целых чисел в сбалансированное бинарное дерево" не только помогает разобраться с основами построения деревьев, но и предоставляет возможность практиковаться в использовании рекурсии. Подобные задачи часто встречаются на собеседованиях и важны для формирования уверенности в решении алгоритмических задач. Рекомендуется попрактиковаться в решении подобных задач для улучшения своих навыков программирования.