Symmetric Tree

Given a binary tree, check whether it is a mirror of itself(ie, symmetric around its center)

For example, this tree is symmetric:

  1.     1
  2.    / \
  3.   2   2
  4.  / \ / \
  5. 3  4 4  3

But the following tree is not.

  1.     1
  2.    / \
  3.   2   2
  4.    \   \
  5.    3    3

题目翻译：
判断一棵树是不是自己的镜像， 根据以上正反两个例子，我想大家都明白这道题的题目要求了，简单明了.

解题思路:
递归:
这道题没什么特别的地方，现在这里简单的分析一下解题思路，从根节点往下，我们要判断三个条件.

  1. 左右两个节点的大小是否相同.
  2. 左节点的左孩子是否和右节点的右孩子相同.
  3. 左节点的右孩子是否和右节点的左孩子相同.

循环:
这道题的难点在于循环解法， 如果是循环解法，我们必须要用到额外的存储空间用于回溯，关键是对于这道题目， 我们要用多少？要怎么用？要用什么样的存储空间？

递归求解，如果以上三个条件对于每一层都满足，我们就可以认为这棵树是镜像树.

时间复杂度:
递归:本质其实就是DFS,时间复杂度为O(n),空间复杂度O(1)
递归:时间复杂度O(n),空间复杂度O(n)

递归代码如下:

  1. /**
  2.  * Definition for binary tree
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     bool isSymmetric(TreeNode *root) {
  13.         if(root == NULL)
  14.             return true;
  15.         return Helper(root->left,root->right);
  16.     }
  18.     bool Helper(TreeNode* left, TreeNode* right)
  19.     {
  20.         if(left == NULL&&right == NULL)
  21.             return true;
  22.         else if(left == NULL||right == NULL)
  23.             return false;
  24.         bool cond1 = left->val == right->val;
  25.         bool cond2 = Helper(left->left,right->right);
  26.         bool cond3 = Helper(left->right, right->left);
  27.         return cond1&&cond2&&cond3;
  28.     }
  30. };

循环解法:
我们主要想介绍一下这道题的循环解法，对于循环，我们要满足对于每一层进行check，代替了递归，一般树的循环遍历，我们都是用FIFO的queue来作为临时空间存储变量的，所以这道题我们也选取了queue，但是我们用两个queue，因为我们要对于左右同时进行检查，很显然一个queue是不够的，具体实现细节，咱们还是看代码吧，，我相信代码更能解释方法.

循环代码如下:

  2. /**
  3.  * Definition for binary tree
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     bool isSymmetric(TreeNode *root) {
  14.        if(root == NULL)
  15.             return true;
  16.         TreeNode* n1 = root->left;
  17.         TreeNode* n2 = root->right;
  18.         if(!n1&&!n2)
  19.             return true;
  20.         if((!n1&&n2)||(n1&&!n2))
  21.             return false;
  22.         queue<TreeNode*> Q1;
  23.         queue<TreeNode*> Q2;
  24.         Q1.push(n1);
  25.         Q2.push(n2);
  26.         while(!Q1.empty() && !Q2.empty())
  27.         {
  28.             TreeNode* tmp1 = Q1.front();
  29.             TreeNode* tmp2 = Q2.front();
  30.             Q1.pop();
  31.             Q2.pop();
  32.             if((!tmp1&&tmp2) || (tmp1&&!tmp2))
  33.                 return false;
  34.             if(tmp1&&tmp2)
  35.             {
  36.                 if(tmp1->val != tmp2->val)
  37.                     return false;
  38.                 Q1.push(tmp1->left);
  39.                 Q1.push(tmp1->right); //note: this line we should put the mirror sequence in two queues
  40.                 Q2.push(tmp2->right);
  41.                 Q2.push(tmp2->left);
  42.             }
  43.         }
  44.         return true;
  45.     }
  46. };