学步园

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.

一个直接的想法是根据原树复制一棵镜像树(即左右交换），然后只要比较两棵树是否相同即可，做镜像和检查相等都比较简单，但复制了一颗树比较代价较高。

我们用另一种更直观的方法：对一颗给定的树root，如果它是一颗对称树，这代表什么呢：

1.root的左孩子和右孩子value相等

2.左孩子的左孩子和右孩子分别和右孩子的右孩子和左孩子对应相等，（完了，这个“孩子”两字答得太多“孩”字越看越奇怪不认识了 *_*)

3.再说通俗点，大家都会判断两棵树是否相等吧：根相等，左和左相等，右和右相等，我们就拿这个改一下就完了，现在的条件是：根相等，左和右相等，右和左相等。

代码如下：

 bool isSymmetric(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
	if (!root )
		return true;
	return check(root->left,root,root->right,root);
    }
bool check(TreeNode* t1,TreeNode* p1,TreeNode* t2,TreeNode* p2)
{
	if (!t1||!t2)
		return !t1&&!t2;
	if (t1->val!=t2->val)
		return false;
	if( (t1==p1->left&&t2==p2->left)||(t1==p1->right&&t2==p2->right))
		return false;
	return check(t1->left,t1,t2->right,t2)&&check(t1->right,t1,t2->left,t2);
}