День 14 Сегодня продолжим говорить про бинарные деревья поиска BST. А именно я предлагаю построить бинарное дерево в коде вам самим. То есть написать все методы работы с деревом. Внизу же, я предлагаю свой вариант реализации этих основных методов. ОСНОВНЫЕ ОПЕРАЦИИ BST • Добавление нового узла (insert); ``` public BST insert(int value) { BST currentNode = this; while (true) { if (currentNode.value > value) { if (currentNode.left == null) { currentNode.left = new BST(value); return this; } else { currentNode = currentNode.left; } } else { if (currentNode.right == null) { currentNode.right = new BST(value); return this; } else { currentNode = currentNode.right; } } } return this; } ``` • Удаление узла по его значению (remove); Добавил в чат, тут не помещается. • Поиск узла по значению (contains); public boolean contains(int value) { BST currentNode = this; while (currentNode != null) { if (value < currentNode.value) { currentNode = currentNode.left; } else if (value > currentNode.value) { currentNode = currentNode.right; } else { return true; } } return false; } Допустим, что так выглядит наше дерево class class BST { public int value; public BST left; public BST right; public BST(int value) { this.value = value; } } ------- ВИДЕО ЛЕКЦИЯ Вот тут как я считаю довольно понятно и доступно разобрали BST. https://www.youtube.com/watch?v=0BUX_PotA4c&ab_channel=AlekOS ------- ЗАДАЧА 1 Lowest Common Ancestor of a Binary Search Tree (Medium $ BST $ Попытка номер 1). Решена со сложностью Time - O(n), Space O(1) за 26 минут при помощи цикла while. Задача была легкой. ------- ЗАДАЧА 2 Binary Tree Level Order Traversal (Medium $ BST $ Попытка номер 1). Решена со сложностью Time - O(n), Space O(n), где n - количество узлов дерева, за 31 минуты при помощи Bread First Search подхода (BFS я рассмотрел вот тут). В целом если знаете этот подход, то задача изи. ------- ВЕСЬ ПРОГРЕСС НА ТЕКУЩИЙ МОМЕНТ: Neetcode Всего 22/75 . easy 12/19. medium 10/49. AlgoExpert Всего 13/200. easy 5/31 medium 8/73. ------- Если вы хотите посмотреть решения данных алгоритм задач или поделится своим мнением, тогда переходите в чат сообщества ▶️ https://t.me/zufarexplainedit Серия постов по подготовке Зуфара к FAANG #Zufar_Faang_Preparation_Notes