Идентичность бинарных деревьев

Задача

Дано: два бинарных дерева. Напишите функцию, которая будет проверять равны ли два бинарных дерева.

Два бинарных дерева являются равными тогда и только тогда, когда их структуры и данные идентичны.

Односвязный список/Singly Linked List

Односвязный список - это абстрактная структура даных, которая имеет следующие свойства:

  1. Последовательные элементы связаны указателем
  2. Последний элемент указывает на null-значение
  3. Может рости в размере
  4. Может быть настолько большим сколько надо (пока не закончится память)
  5. Не тратит лишнюю память

Обход бинарного дерева по уровням

Задача:

Дано: бинарное дерево. Вывод: вывести значения узлов в порядке обхода бинарного дерева по уровням.

К примеру, пусть дано следующее бинарное дерево:

    3
   / \
  9  20
    /  \
   15   7

Максимальная глубина бинарного дерева

Задача:

Дано: бинарное дерево. Найти: максимальную глубину, где максимальная глубина бинарного дерева - это количество нод на самом длинном пути от корневой ноды до самой дальней листовой ноды.

Минимальная глубина бинарного дерева

Задача:

Дано: бинарное дерево. Найти: минимальную глубину, где минимальная глубина бинарного дерева - это количество нод на кратчайшем пути от корневой ноды до ближайшей листовой ноды.

Пересечение двух односвязных списков

Задача:

Припустим существует два односвязных списка, которые пересекаются в некоторой точке и стают односвязным списком. Известно начало обох списков, но неизвестна точка пересечения. Также, не известны длины обеих списков и длины обох списков могут быть разными. Первый список может иметь n элементов, перед тем как он достигнет точки пересечения, а второй - m элементов, где m и n могут быть m = n, m < n, m > n. Реализовать алгоритм нахождения точки пересечения.

Судоку

Задача:

Определить является ли заданый судоку правельным. Правела судоку можна посмотреть здесь.

Доска судоку будет не полностью заполнена, где пустые клетки будут позначены как '.'.

Например, на картинке показан частично заполненный судоку, который является правельным:

Сортировка вставкой/Insertion sort

Сортировка вставкой - это простая и эфективная сортировка. В этом алгоритме каждая итерация удаляет элемент из входних даных (например, массива) и вставляет эго в нужную позицию в уже отсортированный список. Выбор элемента, который будет выдален с входных даных, случайный и процес будет продолжатся пока все елементы не будут отсортированы.

Сортировка выбором/Selection sort

Сортировка выбором - это еще один простой алгоритм сортирования. Сортировка выбором является сортировкой на месте. Полезна на небольших файлах. Используется для сортировки файлов с большими значениями и маленькими ключами. Это потому, что сортировка выбором построена на работе с ключами и обмен елементов применяется только там где необходимо.

Преимущества:

  1. Простой в применении
  2. Сортировка на месте(не использует дополнительного места)

Пузырьковая сортировка/Bubble sort

Пузырьковая сортировка является одним из самых простых алгоритмов сортирования. Хотя многие говорят, что этот алгоритм не стоит даже рассматривать, я бы все равно предпочел написать о нем в паре строк. Алгоритм действительно является плохим в плане производительности и его не стоит использовать в приложениях так, как его сложность в хутшем, да и в лучшем случае, будет О(n^2). Пузырьковая сортировка называется так лиш потому, что больший елемент перемещается в конец массива как пузырек)).