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.

这个题目思路就是BFS啦, 只不过把left child 和right child比较了之后再recursively 比较children的children. 我们用一个helper function, 用于比较tree1, 和tree2, 然后recursive call这个function, 然后返回helper(root, root)即可.

1. Constraints

1) root can be None, return True

2. Ideas

BFS,     T: O(n)   S: O(n)  worst case when tree is linear

3. Code

 class Solution:

     def Symmetric(self, root):

         def helper(tree1, tree2):

             if not tree1 and not tree2:

                 return True

             if tree1 and tree2 and tree1.val == tree2.val:

                 return helper(tree1.left, tree2.right) and helper(tree1.right, tree2.left)

             return False

         return helper(root, root)

4. Test cases

1) root is None

2) root is 1

3)

    1

   / \

  2   2

 / \ / \

3  4 4  3