Алгоритмы - Собеседования, Олимпиады, ШАД: “Задача с собеседования в Яндекс Дано дерево: struct Node { Node *l, *r…”

Задача с собеседования в Яндекс

Дано дерево:

struct Node {
    Node *l, *r;
    int value;
}

Требуется написать функцию, которая проверяет, является ли дерево симметричным

Решение:

Будем рекурсивно спускаться в детей и проверять у каждого узла наличие ребенка. Если у какого-то ребенка есть путь вниз, а у другого нет, то дерево не является симметричным. Также параллельно в спуске будем проверять симметричность значений value

bool isSymmetric(Node* root) {
return root == NULL ? true : isMirrored(root->l, root->r);
}

bool isMirrored(Node* a, Node* b) {
if (a == NULL && b == NULL)
return true;

if (a != NULL && b != NULL)
return a->value == b->value && isMirrored(a->l, b->r) && isMirrored(a->r, b->l);

return false;
}

@algoses