力扣第101题：对称二叉树（C语言解法）

题目描述

给定一个二叉树，检查它是否是镜像对称的。

• 示例1：二叉树 [1,2,2,3,4,4,3] 是对称的。
• 示例2：二叉树 [1,2,2,null,3,null,3] 不是镜像对称的。

解题思路

对于检查二叉树是否对称的问题，我们可以采用递归的方法来解决。基本思路是，对于树中的任意两个节点，如果它们是镜像对称的，那么它们的值应该相等，且它们的左子树和右子树也应该分别是对称的。我们可以定义一个辅助函数 isSymmetric，它接受两个节点作为参数，分别代表树中的两个对应节点，然后递归检查这两个节点以及它们的子节点是否满足对称的条件。

代码详解

#include <stdbool.h>
#include <stdio.h>

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 辅助函数，检查两个节点是否对称
bool Symmetric(struct TreeNode* left, struct TreeNode* right) {
    // 如果两个节点都为空，说明对称
    if (left == NULL && right == NULL) {
        return true;
    }
    // 如果一个为空，一个非空，或者值不相等，说明不对称
    if (left == NULL || right == NULL || left->val != right->val) {
        return false;
    }
    // 递归检查左子树和右子树
    return Symmetric(left->left, right->right) && Symmetric(left->right, right->left);
}

// 主函数，检查二叉树是否对称
bool isSymmetric(struct TreeNode* root) {
    // 空树也是对称的
    if (root == NULL) {
        return true;
    }
    return Symmetric(root->left, root->right);
}

// 测试代码
int main() {
    // 创建测试用的二叉树
    struct TreeNode root;
    root.val = 1;
    root.left = malloc(sizeof(struct TreeNode));
    root.left->val = 2;
    root.right = malloc(sizeof(struct TreeNode));
    root.right->val = 2;
    root.left->left = malloc(sizeof(struct TreeNode));
    root.left->left->val = 3;
    root.left->right = malloc(sizeof(struct TreeNode));
    root.left->right->val = 4;
    root.right->left = malloc(sizeof(struct TreeNode));
    root.right->left->val = 4;
    root.right->right = malloc(sizeof(struct TreeNode));
    root.right->right->val = 3;

    // 检查是否对称
    if (isSymmetric(&root)) {
        printf("The tree is symmetric.\n");
    } else {
        printf("The tree is not symmetric.\n");
    }

    // 释放内存
    free(root.left->left);
    free(root.left->right);
    free(root.right->left);
    free(root.right->right);
    free(root.left);
    free(root.right);

    return 0;
}

• 在实际使用中，需要确保为二叉树的每个节点分配内存，并在使用完毕后释放内存，以避免内存泄漏。
• 递归函数 isSymmetric 需要正确处理边界条件，即当节点为空时的情况。
• 递归的终止条件是两个节点都为空，或者两个节点的值不相等，或者它们的子树不对称。