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

1 class Solution:2     def Symmetric(self, root):3         def helper(tree1, tree2):4             if not tree1 and not tree2:5                 return True6             if tree1 and tree2 and tree1.val == tree2.val:7                 return helper(tree1.left, tree2.right) and helper(tree1.right, tree2.left)8             return False9         return helper(root, root)

 

4. Test cases

1) root is None

2) root is 1

3) 

1   / \  2   2 / \ / \3  4 4  3