Leo Lei | 雷雨
July 28, 2018
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
example 1: symmetric tree
1
/ \
2 2
\ /
4 4
example 2: not a symmetric tree
1
/ \
2 3
/ /
3 2
My first idea was to do a in-order traverse and see if the resulted values are palindromic. However, it didn't work on example 2. In this example, in-order traversal would give [3,2,1,2,3] which is indeed palindromic, but the tree is not symmetric.
The key to tackle the problem is understanding what symmetry means for a tree: two nodes mirror each other should has same val.
It's kind of straightforward doing it recursively, but doing it iteratively, a modified BFS is needed. From example 1, we know that for each level the left side is mirror with the right side. If we wan to check something level by level, a BFS is the first choice. The tricky part is when pushing nodes to the queue, we should push left's left, then right's right, then left's right, finally right's left.
# Recursive
class Solution:
def is_mirror(self, node1, node2):
if not node1 and not node2:
return True
if not node1 or not node2:
return False
return node1.val == node2.val and \
self.is_mirror(node1.left, node2.right) and \
self.is_mirror(node1.right, node2.left)
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.is_mirror(root, root)
# Iterative
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
q = collections.deque([root, root])
while q:
n1, n2 = q.popleft(), q.popleft()
if not n1 and not n2:
continue
if not n1 or not n2:
return False
if n1.val != n2.val:
return False
q.append(n1.left)
q.append(n2.right)
q.append(n1.right)
q.append(n2.left)
return TruePython requests deep dive I came cross to a situation where I needed to send lots requests to a host to pull data. The reason why I couldn't send a single request to get what I wanted is the dataset is huge and the query may simple timeout. I broke the dataset into small parts and combined all parts together thereafter.
Two things I found quite useful for performance increase:
- reuse TCP connection
- make parallel calls
Reuse TCP connection with Session Object when making requests to the same host.
The Session object allows you to persist certain parameters across requests. It also persists cookies across all requests made from the Session instance, and will use urllib3’s connection pooling.