【数据结构与算法经典例题】判断二叉树是否对称

倔强的石头_

发布于 2024-12-06 19:25:38

1980

文章被收录于专栏：C/C++指南C/C++指南

一、问题描述

给你一个二叉树的根节点 root ，检查它是否轴对称。 原题出自 101. 对称二叉树 - 力扣（LeetCode）

二、解题思路

判断一颗二叉树是否对称的解题思路可以通过比较两个子树是否镜像对称来实现。 具体地说，如果一棵树的左子树与右子树是镜像对称的，那么这棵树就是对称的。这个问题可以通过递归来解决。 解题思路如下：

首先，比较根节点：如果二叉树为空，那么它是对称的（空树是对称的）。如果二叉树只有一个节点（即根节点），那么它也是对称的。
其次，递归地比较左子树和右子树：对于非空树，我们需要递归地比较它的左子树和右子树。具体来说，我们需要先比较左子树和右子树的结构和数据是否相同，然后再交叉比较左子树的左子树和右子树的右子树，以及左子树的右子树和右子树的左子树。
递归终止条件：在递归过程中，如果两个节点都为空，那么它们是对称的。如果只有一个节点为空，或者两个节点的值不相等，那么它们不是对称的。
要注意的是解决这个问题需要两个函数实现:
第一个函数接收一个树的根结点，判断树是否空以及调用子函数；
第二个函数接收两个节点的值进行对比，这两个节点可能是左子树的根和右子树的根，也可能是左子树的右子树和右子树的左子树，或是左子树的左子树和右子树的右子树

三、C语言实现代码

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    
};
typedef struct TreeNode TNode;

bool _isSymmetric(TNode* root1, TNode* root2)//子树判断函数
{
    if (root1 == NULL && root2 == NULL)
        return true;
    if (root1 == NULL || root2 == NULL)//结构对比
        return false;
    if (root1->val != root2->val)//数据对比
        return false;
    return _isSymmetric(root1->left, root2->right)//对左右子树的节点交叉判断
        && _isSymmetric(root1->right, root2->left);
}
bool isSymmetric(struct TreeNode* root)
{
    if (root == NULL)
        return true;
    return _isSymmetric(root->left, root->right);//调用子函数
}