题目描述:
给定两个二叉树，检查它们是否呈镜像对称，即树的结构成轴对称，且对应节点的节点值相同。
输入格式
第一棵树的输入在第11行，表示二叉树的前序遍历序列。
第二棵树的输入在第22行，表示二叉树的前序遍历序列。
节点值的范围为[0,100][0,100]区间内的整数，输入中的−1−1表示空节点。
输出格式
输出YES表示两颗二叉树镜像对称，输出NO表示两棵树不对称。
#include <iostream> using namespace std; struct TreeNode { int data; TreeNode *leftchild, *rightchild; TreeNode() :leftchild(NULL), rightchild(NULL) {} TreeNode(int x, TreeNode * l = NULL, TreeNode * r = NULL) :data(x),leftchild(l), rightchild(r) {} }; class Tree { protected: TreeNode * root; void Print(TreeNode* subtree); void Create(TreeNode * & subtree); public: Tree():root(NULL){} void Create() { Create(root); }; void Print() { Print(root); } friend void Bool(Tree & tree1, Tree & tree2); }; bool equal(TreeNode * a, TreeNode * b)//比较当前节点值及节点a的左(右)子树与节点b的右(左)子树是否相等 { if (a == NULL && b == NULL)return true; if (a != NULL && b != NULL && a->data == b->data&&equal(a->leftchild, b->rightchild) && equal(a->rightchild, b->leftchild)) return true; else return false; } void Bool(Tree & tree1, Tree & tree2) { if (equal(tree1.root, tree2.root)) cout << "YES"; else cout << "NO"; } void Tree::Create(TreeNode * & subtree)//前序遍历递归建立二叉树 { int x; if(cin>>x) { if (x != -1) { subtree = new TreeNode(x); Create(subtree->leftchild); Create(subtree->rightchild); } else subtree = NULL; } } void Tree::Print(TreeNode * subtree) { if (subtree != NULL) { cout << subtree->data << " "; Print(subtree->leftchild); Print(subtree->rightchild); } else cout << "-1" << " "; } int main() { Tree tree1, tree2; tree1.Create(); tree2.Create(); Bool(tree1, tree2); //tree.Print(); //std::cout << "Hello World!\n"; }
