Leetcode101. 对称二叉树

2021年5月10日 253点热度 1人点赞 0条评论

题目描述

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

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

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

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

    1
   / \
  2   2
   \   \
   3    3

进阶:

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

解题思路

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

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

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

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

示例代码

递归版本:

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);
}

迭代版本:

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);
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论