#
一天一道LeetCode本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处
##（一）题目
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 /
2 2 / \ /
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/
2 2
\
3 3
Note: Bonus points if you could solve it both recursively and iteratively.
##（二）解题
本题大意：判断一颗树是不是左右对称
解题思路一：分别求二叉树的前序和后序遍历，他们是互为反转数组。
/**
* 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:
bool isSymmetric(TreeNode* root) {
vector<int> pre;
vector<int> post;
preOrderTree(root , pre);
postOrderTree(root , post);
for(int i = 0 ,j=post.size()-1; i<pre.size(),j>=0;i++,j--)//一个正向，一个反向
{
if(pre[i] != post[j]) return false;//不相等就返回false
}
return true;
}
void preOrderTree(TreeNode* root , vector<int> &pre)//前序遍历
{
if(root==NULL) {pre.push_back(0);return;}
pre.push_back(root->val);
preOrderTree(root->left,pre);
preOrderTree(root->right,pre);
}
void postOrderTree(TreeNode* root , vector<int> &post)//后续遍历
{
if(root==NULL) {post.push_back(0);return;}
postOrderTree(root->left,post);
postOrderTree(root->right,post);
post.push_back(root->val);
}
};
解题思路二：将前序遍历和后序遍历合起来一起考虑，对于一个节点，如果他们相等，就判断左右子树是否为镜像！
/**
* 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:
bool isSymmetric(TreeNode* root) {
return isMirror(root,root);
}
bool isMirror(TreeNode* root1,TreeNode* root2)
{
if(root1==NULL) return root2==NULL;
if(root2==NULL) return false;
if(root1->val!=root2->val) return false;
return isMirror(root1->left,root2->right) && isMirror(root1->right,root2->left);//左子树和右子树是否成镜像
}
};