JuniorКодОчень частоЕщё не отвечали
Проверка симметричности бинарного дерева
Дан корень бинарного дерева. Верните, является ли оно зеркальным отражением самого себя (симметричным относительно центра).
Требования:
- Сравнивайте левое и правое поддеревья как зеркала; пустое дерево симметрично.
struct Node { Node* l; Node* r; int value; };
bool isSymmetric(Node* root) {
// ваш код здесь
}Допишите реализацию.
Симметрия — зеркальное свойство двух поддеревьев, а не одного узла. Рекурсивно сравнивайте left с right: два узла зеркальны тогда и только тогда, когда их значения равны и left.l зеркален right.r, а left.r зеркален right.l. Оба null — симметрично; один null — нет. Пустое дерево симметрично. O(n) время.
- ✗Сравнивать двух детей одного узла вместо зеркалирования между двумя поддеревьями
- ✗Считать «один null, один есть» совпадением вместо отказа
- ✗Полагаться на палиндром обхода, который проходит и для несимметричных деревьев
- →Почему сравнения собственных левого и правого детей узла недостаточно?
- →Как написать это итеративно с очередью?
Оглавление
Задача
Проверьте, симметрично ли бинарное дерево относительно центра. За O(n).
Решение
struct Node { Node* l; Node* r; int value; };
static bool mirror(Node* a, Node* b) {
if (!a && !b) return true; // оба пусты — зеркально
if (!a || !b) return false; // только один пуст — нет
return a->value == b->value
&& mirror(a->l, b->r) // внешние стороны
&& mirror(a->r, b->l); // внутренние стороны
}
bool isSymmetric(Node* root) {
return root == nullptr || mirror(root->l, root->r);
}Ключевые моменты
- Зеркалим между поддеревьями:
a->lсb->r,a->rсb->l. - Сравнение собственных детей одного узла недостаточно для глобальной симметрии.
- Пустое дерево и пара null считаются симметричными; один null — отказ.
Оглавление
