Поправляем бинарное дерево
Задача. Дано бинарное дерево с небольшим дефектом. В этом дереве есть один "дефектный" узел, правый дочерний узел которого неверно указывает на другой узел, расположенный на той же глубине, но правее недопустимого узла.
Необходимо удалить этот дефектный узел и все узлы под ним, за исключением узла, на который он неверно указывает), смотрите пример ниже.
Примечание: 7 - дефектный узел, удаляем его и его подузлы: 2.
Разбор
Заведем глобальный хэш-сет, куда будем записывать посещенные узлы дерева.
Далее рекурсивно пройдем по дереву, начиная обход на каждом уровне с правого узла. Таким образом, если мы встретим правый узел, который уже обрабатывали, то мы нашли искомый "дефектный" узел, который и нужно удалить.
Детали реализации смотрите ниже.
Реализация
public static TreeNode FixBinaryTree(TreeNode root)
{
if (root == null) {
return null;
}
if (root.right != null && Visited.Contains(root.right.val)) {
return null;
}
Visited.Add(root.val);
root.right = FixBinaryTree(root.right);
root.left = FixBinaryTree(root.left);
return root;
}https://gist.github.com/unilecs/de33a57711c2943b01f9fb65da58229f