- 题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
- 题目解答
首先想到的便是用递归算法来做。首先判断根结点是否为空；其次判断其左右子树，判断左子树的左结点是否等于右子树的右结点，以及左子树的右结点是否等于右子树的左结点。
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if (pRoot == NULL)
return true;
return comp(pRoot->left, pRoot->right);
}
bool comp(TreeNode* l, TreeNode* r){
if (l == NULL)
return r == NULL;
if (r == NULL)
return l == NULL;
if (l->val != r->val)
return false;
return comp(l->right, r->left) && comp(l->left, r->right);
}
};
还有一种方法，可以用任意一种遍历方式（前序、中序、后序、层次遍历）分别进行从左到右和从右到左的遍历，两次遍历结果一样就说明这棵树是对称的。下面的代码基于层次遍历。
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if (pRoot == NULL)
return true;
queue<TreeNode*> q1, q2;
TreeNode* l, *r;
q1.push(pRoot->left);
q2.push(pRoot->right);
while (!q1.empty() && !q2.empty()){
l = q1.front(); q1.pop();
r = q2.front(); q2.pop();
if (l == NULL && r == NULL)
continue;
if (l == NULL || r == NULL)
return false;
if (l->val != r->val)
return false;
q1.push(l->left);
q1.push(l->right);
q2.push(r->right);
q2.push(r->left);
}
return true;
}
};
下面的代码是基于先序遍历的递归算法。
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
return isSymmetrical(pRoot,pRoot);
}
bool isSymmetrical(TreeNode* pRoot1,TreeNode* pRoot2)
{
if(pRoot1==NULL&&pRoot2==NULL)
return true;
if(pRoot1==NULL || pRoot2==NULL)
return false;
if(pRoot1->val!=pRoot2->val)
return false;
return isSymmetrical(pRoot1->left,pRoot2->right) && isSymmetrical(pRoot1->right,pRoot2->left);
}
};