对称美学：如何判断一颗二叉树是否对称？_判断二叉树是否对称c语言

本篇博客会讲解力扣“101. 对称二叉树”的解题思路，这是题目链接。先来审题：

本题若使用C语言实现，最简单的方式是使用递归，把大问题化作小问题。

一棵二叉树对称当且仅当左子树和右子树镜像对称，所以问题转换为如何判断两棵树p和q是否镜像对称。

判断p和q是否镜像对称的方法是：p和q镜像对称当且仅当p和q的根结点的值相等，且p的左子树和q的右子树镜像对称，p的右子树和q的左子树镜像对称。

递归的终止条件是：若p和q都是空树，则显然镜像对称。若p和q中，一棵是空树，另一棵不是空树，则不满足镜像对称的条件。

代码如下：

// 判断2棵树是否镜像对称
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{
    // 若2棵树都是空树，则镜像对称
    if (p == NULL && q == NULL)
    {
        return true;
    }

    // 此时至少1棵非空
    // 若2棵树一颗为空，另一棵非空，则不镜像对称
    if (p == NULL || q == NULL)
    {
        return false;
    }

    // 此时2棵都非空
    // 2棵树镜像对称当且仅当根结点相同，
    // 且p的左树和q的右树镜像对称，p的右树和q的左树镜像对称
    return p->val == q->val
        && _isSymmetric(p->left, q->right)
        && _isSymmetric(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root){
    // 若左树和右树镜像对称，则为对称二叉树
    return _isSymmetric(root->left, root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

轻松通过。

总结

善于转换问题，把大问题化作小问题，是解题的关键。本题的关键是把一棵数镜像对称转换成两棵树镜像对称的问题，再转换成两棵树的左右子树镜像对称的问题。

感谢大家的阅读！