对称二叉树（递归或迭代）

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [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

说明：如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

分析：判断一颗二叉树是不是对称的，等价于判断其左右子树是不是镜像对称的，即判断对称的位置上的元素是不是相等。

两个节点A和B对称等价于: 

• 这两个节点上存储的值相等
• 节点A的左子树节点和节点B的右子树上的节点是对称的
• 节点A的右子树节点和节点A的左子树上的节点是对称的

 递归代码如下：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL)
            return true;
        return isSymmetric(root->left, root->right);
    }
    //以root1为根的二叉树与以root2为根的二叉树是否是镜像二叉树。
    bool isSymmetric(TreeNode* root1, TreeNode* root2)
    {
        if (root1 == NULL && root2 == NULL)
            return true;
        if (root1 == NULL || root2 == NULL || root1->val != root2->val)
            return false;
        return (isSymmetric(root1->left, root2->right) && isSymmetric(root1->right, root2->left));
    }
};

迭代：

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;
    }
 
};