Leetcode101. 对称二叉树

题目描述

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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

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

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

解题思路

首先，观察一下什么样的树是对称的。不难发现，如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

更具体地说，如果两个树要镜像对称，那么就要同时满足下面的条件：

  • 他们的两个根节点的值相同
  • 每个树的左子树与另一个树的右子树镜像对称
  • 每个树的右子树与另一个树的左子树镜像对称

据此可以写出递归和迭代版本的代码。

示例代码

递归版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool check1(TreeNode* p,TreeNode* q)
{
    if(p==nullptr&&q==nullptr) return true;
    if((p==nullptr&&q!=nullptr)||(p!=nullptr&&q==nullptr))
    {
        return false;
    }
    if((p->val == q->val )&& check1(p->left,q->right) && (check1(p->right,q->left)))
    {
        return true;
    }
    return false;
}

bool isSymmetric(TreeNode* root)
{
    return check1(root,root);
}

迭代版本：

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
29
30
bool check2(TreeNode* p,TreeNode* q)
{
    queue<TreeNode*>qu;
    qu.push(p);
    qu.push(q);
    while(!qu.empty())
    {
        p=qu.front();
        qu.pop();
        q=qu.front();
        qu.pop();

        if(p==nullptr && q==nullptr) continue;
        if(p==nullptr||q==nullptr) return false;
        if(p->val!=q->val) return false;

        qu.push(p->left);
        qu.push(q->right);

        qu.push(p->right);
        qu.push(q->left);
    }
    return true;
    
}

bool isSymmetric(TreeNode* root)
{
    return check2(root,root);
}