101. Symmetric Tree
https://leetcode.com/problems/symmetric-tree/description/
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 | 1 |
But the following [1,2,2,null,3,null,3] is not:
1 | 1 |
Note:
Bonus points if you could solve it both recursively and iteratively.
Solution:
iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None: return True
q1 = [root]
q2 = [root]
pointer = 0
while (pointer < len(q1)):
l = q1[pointer]
r = q2[pointer]
# both none
if (l is None and r is None):
pointer += 1
continue
# one none
if (l is None or r is None):
return False
# equal
if (l.val == r.val):
q1 = q1 + [l.left, l.right]
q2 = q2 + [r.right, r.left]
pointer += 1
continue
# not equal
if (l.val != r.val):
return False
return True
recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None: return True
return isMirror(root.left, root.right)
def isMirror(l,r):
if (l is None) and (r is None): return True
if (l is None) or (r is None): return False
if (l.val == r.val) and (isMirror(l.left, r.right)) and (isMirror(l.right, r.left)): return True
return False