алгоритм проверки симметричного дерева с использованием рекурсии только с одним параметром функции

Question

Я ищу алгоритм, чтобы проверить, является ли дерево симметричным или не использует рекурсию по функции только с одним параметром, который является корневым узлом. Я видел этот вопрос в leetcode, который имеет простой ответ, если функция имеет два параметра (root-> left и root-> right), но я пытаюсь выяснить алгоритм со строго одним параметром.

bool isSymmetric(TreeNode* root) {
        if(root==NULL || (root->left==NULL && root->right==NULL)){
            return true;
        } 

        if(root->left!=NULL && root->right!=NULL){
            return (isSymmetric(root->left) && isSymmetric(root->right));
        }
        return false;
}

У меня естьпопробовал данный код, но он не проверяет, равны ли значения симметричных узлов. Возможно ли решение моей проблемы?

Answer 1

Я предполагаю, что под "симметричным" вы подразумеваете, что левая сторона дерева является зеркальным отображением правой стороны дерева. Другими словами, все значения на левой стороне отражаются одинаковыми значениями на правой стороне. Вот пример такого дерева:

    1
   / \
  2   2
 /\   /\
3  4 4  3

Поскольку сравниваемые узлы могут быть широко разделены в дереве, это требует передачи двух указателей узлов в функцию рекурсивной проверки. Однако вы можете вызвать эту функцию из функции, которая получает единственный указатель на корень дерева:

// Helper function to recursively check if two branches are mirror images
static bool areMirrored(TreeNode* left, TreeNode* right) {
    if (left == NULL)
        return (right == NULL);
    if (right == NULL)
        return false;
    if (left->value != right->value)
        return false;
    return (areMirrored(left->left, right->right) &&
            areMirrored(left->right, right->left));
}

// Check if tree is symmetric (left and right branches are mirror images)
bool isSymmetric(TreeNode* root) {
    return (root == NULL || areMirrored(root->left, root->right));
}

РЕДАКТИРОВАТЬ: Вот версия, которая использует «поддельный» корневой узел на каждом шагерекурсии. Недостаток использования дополнительного хранилища для хранения поддельного узла на каждом уровне рекурсии:

bool isSymmetric(TreeNode* root) {
    TreeNode fake;

    if (root == NULL)
        return true;
    if (root->left == NULL)
        return (root->right == NULL);
    if (root->right == NULL)
        return false;
    if (root->left->value != root->right->value)
        return false;

    fake.value = 0; // fake value isn't used
    fake.left = root->left->left;
    fake.right = root->right->right;
    if (!isSymmetric(&fake))
        return false;

    fake.left = root->left->right;
    fake.right = root->right->left;
    return isSymmetric(&fake);
}

Answer 2

Просто замените

return (isSymmetric(root->left) && isSymmetric(root->right));

на

return (isSymmetric(root->left) && isSymmetric(root->right) && root->left->value == root->right->value);

Не знаете, как в вашем коде назван элемент value, но вы поняли идею.