给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
分析
判断一棵二叉树本身是否是镜像对称的，这个问题可以转化为：二叉树的左子树与右子树是否是镜像对称的。
问题一经转化，就有一种似曾相识的感觉，上一篇文章刚分析过判断两棵二叉树是否相等的问题，而这道题只不过是把“相等”换为“对称”，方法其实是一样的！
本题的解法同样有递归和迭代两种方法：
（设二叉树左子树为p，右子树为q，p、q均指向左右子树的根）
递归：p和q的值相等，并且p的左子树与q的右子树对称，p的右子树与q的左子树对称
迭代：维护一个栈，方法与上一篇文章中判断二叉树是否相等类似，只不过，我们在将节点入栈的时候，顺序不是 p->left , q->left ,p->right ,q->right，而是p->left , q->right , p->right ,q->left，为什么？因为我们要判断的是对称，所以p->left 对应q->right，p->right 对应q->left，它们的入栈顺序理应如此。
C++ 递归
/**
* 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) {
if(!root) return true; //空树是对称的
return symmetric(root->left,root->right);
}
private:
bool symmetric(TreeNode *p,TreeNode *q) /*判断两棵树是否对称*/
{
if(!p && !q) return true; //都是空
if(!p || !q) return false; //只有一个空
return (p->val==q->val)&&symmetric(p->left,q->right) && symmetric(p->right,q->left);
/*树p和树q对称的条件：p和q的值相同，并且p的左子树与q的右子树对称，p的右子树与q的左子树对称*/
}
};
C++ 迭代
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if(!root) return true; //空树是对称的
stack<TreeNode *> s;
TreeNode *p=root->left,*q=root->right;
s.push(p);
s.push(q); //即使是空节点，也是可以push到栈里的，栈并不为空。
while(!s.empty())
{
p=s.top();s.pop();
q=s.top();s.pop();
if(!p && !q) continue; //p、q都是空节点
if(!p || !q) return false; //有一个为空，不对称
if(p->val!=q->val) return false; //值不相等，不对称
s.push(p->left);s.push(q->right);
s.push(p->right);s.push(q->left);
}
return true;
}
};
————————————————
版权声明：本文为CSDN博主「wepon_」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u012162613/article/details/41213149
