Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3
But the following is not:
1 / \ 2 2 \ \ 3 3
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.
Tree Depth-first Search
Have you met this question in a real interview?
Yes
No
这道题开始想法是，对根结点的两个左右子树分别的进行先序遍历，然后将得到的结果存放在数组之中，这之后再进行比较，看是否相等，但是这样
做有个问题1,2,2，#，3，#，3这种情况下，他是不对称的，但按我这种做法，还是相等：
#include<iostream>
#include<stack>
#include <vector>
using namespace std;
// Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//前序遍历
void first_search(TreeNode* root,vector<int>& temp)
{
if(root==NULL)
return;
temp.push_back(root->val);
if(root->left!=NULL)
first_search(root->left,temp);
else
temp.push_back('#');
if(root->right!=NULL)
first_search(root->right,temp);
else
temp.push_back('#');
return;
}
bool isSymmetric(TreeNode *root) {
if(root==NULL)
return 1;
vector<int> temp1,temp2;
first_search(root->left,temp1);
first_search(root->right,temp2);
if(temp1==temp2)
return 1;
else
return 0;
}
int main()
{
}
采用递归的方法来做，判断两边的两个左右子树是否对称，即判断左子树的左子树是否等于右子树的右子树，左子树的右子树是否等于右子树的左子树，然后选取合适的递归终止条件，即当两个左右子树的西面没有结点（返回），或者两边各有一个节点（接着递归），四个结点（接着递归），或者其他情况（返回），还有注意的是最后返回时要判断下这两个值是否相等
下面是AC的代码：
#include<iostream>
//#include<stack>
#include<queue>
#include <vector>
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 ifduicheng(TreeNode* left_root,TreeNode* right_root)
{
if(left_root->left==NULL&&left_root->right==NULL&&right_root->left==NULL&&right_root->right==NULL)
{
if(left_root->val==right_root->val)
return true;
else
return false;
}
else if(left_root->left!=NULL&&left_root->right!=NULL&&right_root->left!=NULL&&right_root->right!=NULL)
{
if(ifduicheng(left_root->left,right_root->right)&&ifduicheng(left_root->right,right_root->left))
{
if(left_root->val==right_root->val)
return true;
else
return false;
}
else
return false;
}
else if(left_root->left!=NULL&&left_root->right==NULL&&right_root->left==NULL&&right_root->right!=NULL)
{
if(ifduicheng(left_root->left,right_root->right))
{
if(left_root->val==right_root->val)
return true;
else
return false;
}
else
return false;
}
else if(left_root->left==NULL&&left_root->right!=NULL&&right_root->left!=NULL&&right_root->right==NULL)
{
if(ifduicheng(left_root->right,right_root->left))
{
if(left_root->val==right_root->val)
return true;
else
return false;
}
else
return false;
}
else
return false;
}
bool isSymmetric(TreeNode *root)
{
if(root==NULL)
return true;
if(root->left==NULL&&root->right==NULL)
return true;
if((root->left==NULL&&root->right!=NULL)||(root->left!=NULL&&root->right==NULL))
return false;
if(root->left!=NULL&&root->right!=NULL)
return ifduicheng(root->left,root->right);
}
int main()
{
TreeNode* root;
root=(TreeNode*)malloc(sizeof(TreeNode));
root->val=1;
root->left=(TreeNode*)malloc(sizeof(TreeNode));
root->left->val=2;
root->right=(TreeNode*)malloc(sizeof(TreeNode));
root->right->val=2;
root->left->left=NULL;
root->left->right=NULL;
root->right->left=NULL;
root->right->right=NULL;
cout<<isSymmetric(root)<<endl;
}