题目描述
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
But the following is not:
Note:
Bonus points if you could solve it both recursively and iteratively.
confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".
题目大意
判断一棵树是否是对称树。
要注意，对称树是一棵树的左右子树互为镜面；
所以是左子树的左孩子==右子树的右孩子。
这点要区别于相等树。
相等二叉树：左子树的左孩子==右子树的左孩子
思路
可以用递归也可以把递归改成非递归（所有的递归都可以改写成非递归的形式）。
不管递归还是非递归，判断条件都是一样的，
（1）首先判断当前结点是否为NULL，如果都为NULL，显然是相等的，
（2）如果不是两棵树的当前结点都为NULL，其中有一个为NULL，那么两棵树必不相等，
（3）如果两棵树的两个结点的值不相等，那么两棵树必不相等。条件判断完后，说明当前结点相等且不为NULL。接下来就再判断当前结点的左右子树，在递归方法中，用递归手段去判断；在非递归方法中，将当前结点的左右孩子结点入队，在去循环判断。由此可见，递归、非递归，思想是一样的。
但是在入队的时候要注意，因为是判断是否是镜像树，所以一棵树以左右孩子子树的顺序入队，另一棵树要以右左孩子的顺序入队。
代码
递归
#include<iostream>
#include<queue>
using namespace std;
// Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool isSymmetric(TreeNode *root)
{
if(root == NULL)return true;
return help_fun(root->left, root->right);
}
bool help_fun(TreeNode *root1, TreeNode *root2)
{
if(root1==NULL && root2==NULL)return true;
else if(root1==NULL || root2==NULL)return false;
else if(root1->val != root2->val)return false;
// 注意：第一棵树的左孩子与第二颗树的右孩子比较
// 第二颗树的右孩子与第一棵树的左孩子相比较
return help_fun(root1->left, root2->right) && help_fun(root1->right, root2->left);
}
int main()
{
return 0;
}
非递归
#include<iostream>
#include<queue>
using namespace std;
// Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
typedef TreeNode* tree;
bool isSymmetric(TreeNode *root)
{
if(root == NULL)return true;
queue<tree> q1, q2;
// 把根结点的左右子树分别看成一棵树，判断这两棵树是否对称
q1.push(root->left);
q2.push(root->right);
while(!q1.empty() && !q2.empty())
{
tree tmp1 = q1.front();
tree tmp2 = q2.front();
// 记得出队
q1.pop(); q2.pop();
// 当前结点都为NULL，就继续去比较队内其他结点
if(tmp1==NULL && tmp2==NULL)continue;
// 只有一个结点为NULL，另一个结点非NULL，必不对称
else if(tmp1==NULL || tmp2==NULL)return false;
// 结点值不相等，必不对称
else if(tmp1->val != tmp2->val)return false;
// 前面三个判断条件都没有走，说明tmp1和tmp2都非NULL
// 就把他们的左右孩子入队
// 注意：第一个入队顺序为：1. 左 2. 右
q1.push(tmp1->left);
q1.push(tmp1->right);
// 注意：第二个入队顺序为：1. 右 2. 左
q2.push(tmp2->right);
q2.push(tmp2->left);
}
// 两个队列有一个非NULL，说明必不对称
if(!q1.empty() || !q2.empty())return false;
return true;
}
int main()
{
return 0;
}
以上。
