《剑指offer》:[59]对称的二叉树
栏目：php教程时间：2016-08-29 08:30:01
题目；请实现1个函数，用来判断1棵2叉树是否是对称的。如果1颗2叉树和它的镜像1样，那末它是对称的。
具体是实现代码以下：
例如，下面2棵树图（1）就是对称的2叉树，而图（2）（3）就不是的。
具体是实现代码以下：
#include <iostream>
using namespace std;
struct BinaryTree
{
int data;
BinaryTree *pLeft;
BinaryTree *pRight;
};
BinaryTree *pRoot1=NULL;
BinaryTree *pRoot2=NULL;
BinaryTree *pRoot3=NULL;
void CreateTree(BinaryTree * &root)
{
int data;
cin>>data;
if(0==data)
root=NULL;
else
{
root=new BinaryTree;
root->data=data;
//前序遍历构建2叉树；
CreateTree(root->pLeft);
CreateTree(root->pRight);
}
}
bool IsSymmetricalHelp(BinaryTree *root1,BinaryTree *root2)
{
if(root1==NULL && root2==NULL)
return true;
if(root1==NULL || root2==NULL)//把null也算上，很重要，避免数据1样的特殊情况；
return false;
if(root1->data!=root2->data)
return false;
return IsSymmetricalHelp(root1->pLeft,root2->pRight)
&& IsSymmetricalHelp(root1->pRight,root2->pLeft);
}
bool IsSymmetrical(BinaryTree *root)
{
return IsSymmetricalHelp(root,root);
}
void PreOrder(BinaryTree *root)
{
if(root)
{
cout<<root->data<<" ";
PreOrder(root->pLeft);
PreOrder(root->pRight);
}
}
void UntiPreOrder(BinaryTree *root)
{
if(root)
{
cout<<root->data<<" ";
PreOrder(root->pRight);
PreOrder(root->pLeft);
}
}
int main()
{
bool result=false;
CreateTree(pRoot1);
cout<<"树1的--前序遍历：";
PreOrder(pRoot1);
cout<<endl;
cout<<"树1的反前序遍历：";
UntiPreOrder(pRoot1);
result=IsSymmetrical(pRoot1);
if(result)
cout<<endl<<"该树是对称树！"<<endl;
else
cout<<"该树不是对称树！"<<endl;
cout<<endl;
CreateTree(pRoot2);//树3虽然遍历1样，但是否是对成树！
cout<<"树2的--前序遍历：";
PreOrder(pRoot2);
cout<<endl;
cout<<"树2的反前序遍历：";
UntiPreOrder(pRoot2);
cout<<endl;
result=IsSymmetrical(pRoot2);
if(result)
cout<<"该树是对称树！"<<endl;
else
cout<<"该树不是对称树！"<<endl;
cout<<endl;
system("pause");
return 0;
}
运行结果以下；
------分隔线----------------------------
------分隔线----------------------------