Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
在下写的代码比较长，但是思路是很简单的，因为先序遍历和中序遍历可以确定一棵树，只需比较两颗树的先序和中序即可，但是还要注意一点，为空节点赋一个值，要不然在树不等的情况下，中序和先序也会相等。比如[1 1]和[1 NULL 1]。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> pre;
vector<int> mid;
bool isSameTree(TreeNode* p, TreeNode* q) {
vector<int> ppvet;
vector<int> qpvet;
vector<int> pmvet;
vector<int> qmvet;
prem(p);
ppvet = pre;
pre.clear();
prem(q);
qpvet = pre;
midd(p);
pmvet = mid;
mid.clear();
midd(q);
qmvet = mid;
/*for (int i = 0; i < pmvet.size(); i++)
cout << pmvet[i] << endl;
for (int i = 0; i < qmvet.size(); i++)
cout << qmvet[i] << endl; */
if (ppvet == qpvet&&pmvet == qmvet)
return true;
else
return false;
}
void prem(TreeNode * root)
{
if (root == NULL)
return ;
pre.push_back(root->val);
if (root->left)
{
pre.push_back(root->left->val);
prem(root->left);
}
else
{
pre.push_back(-1);
prem(root->left);
}
if (root->right)
{
pre.push_back(root->right->val);
prem(root->right);
}
else
{
pre.push_back(-1);
prem(root->right);
}
}
void midd(TreeNode * root)
{
if (root == NULL)
return;
if (root->left)
{
mid.push_back(root->left->val);
midd(root->left);
}
else
{
mid.push_back(-1);
midd(root->left);
}
mid.push_back(root->val);
if (root->right)
{
mid.push_back(root->right->val);
midd(root->right);
}
else
{
mid.push_back(-1);
midd(root->right);
}
}
};