整理自剑指Offer
一：题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
二：解题思路
看到这个题第一反应是求二叉树的镜像二叉树，然后同时遍历两个树，进行比较
遇到问题 ：在求二叉树的镜像二叉树改变了原始的二叉树的结构，不可行
剑指Offer的解法：
如上图，我们可以看出第一个二叉树是对称的，第二棵与第三棵是不对称的
对树的遍历有三种方式：前序遍历，中序遍历，后序遍历，在这三种方法中都是先遍历左子结点再遍历右子节点。
是否可以定义一种新的遍历方式，先遍历右子节点再遍历左子结点
如先序遍历：父结点，左子结点，右子节点
定义的基于先序遍历的新的遍历方式：父结点，右子节点，左子结点
如果两者输出的结果相同，则说明这个二叉树是对称的
如上图第一棵树：
先序遍历 8、6、5、7、6、7、5
新的遍历8、6、5、7、6、7、5
对称
第二棵树：
先序遍历：8、6、5、7、9、7、5
新的遍历：8、9、5、7、6、7、5
不对称
第三棵树
先序遍历：7、7、7、7、7、7
新的遍历：7、7、7、7、7、7
对称？不对
如何解决这个问题：将叶子节点的NULL加入其中就可以解决
第三棵树：
先序遍历：7、7、7、NULL、NULL、7、NULL、NULL、7、7、NULL、NULL、NULL
新的遍历：7、7、NULL、7、NULL、NULL、7、NULL、NULL、7、NULL、NULL
不对称
三：代码实现
递归版代码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetricalCore(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;
//阶梯思想容易理解，但是递归的代码不易理解
//可以将pRoot1看成是先序遍历的指针，先左后右
//可以将pRoot2看成是新的遍历的指针，先右后左
//如果两者相同，比较下一个对称位置的结点
//如果不相等，返回false
return isSymmetricalCore(pRoot1->left,pRoot2->right)&&
isSymmetricalCore(pRoot1->right,pRoot2->left);
}
bool isSymmetrical(TreeNode* pRoot)
{
//递归版本
//根节点为空指针,认为是对称的
if(pRoot==NULL)
return true;
return isSymmetricalCore(pRoot,pRoot);
}
};
非递归版代码--队列方式实现
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot==NULL)
return true;
//利用两个队列保存两种遍历的结果,队列先进先出
//q1:先序遍历结果 q2:新的遍历的结果
queue<TreeNode*>q1,q2;
TreeNode *left,*right;
//入队
q1.push(pRoot->left); //先左后右
q2.push(pRoot->right); //先右后左
while(!q1.empty() && !q2.empty()){
left=q1.front(); //取队首元素
q1.pop(); //出队
right=q2.front();
q2.pop();
//对称位置均空，继续
if(left==NULL && right==NULL)
continue;
//对称位置一空一不空，不对称
if(left==NULL || right==NULL)
return false;
//对称位置值不相同，不对称
if(left->val!=right->val)
return false;
q1.push(left->left);
q1.push(left->right);
q2.push(right->right);
q2.push(right->left);
}
return true;
}
};