Hello everybody, ↵
[INTRO]↵
this blog series is the first of many as my attempt to become an expert on code- forces before my fourth year of university is over.↵
I'mcurrently studying in my third year and about to finish my third year of studying computer engineering.↵
iI know I might be a bit late to the party but better late than never!↵
↵
this is proof to myself that I can dio anything.↵
[TOPIC] ↵
Serialization of a binary tree:↵
the problem I tried to solve using bfs, having to cover each level where a level is at most 2^n nodes, making the serialization process intensive to say the least↵
Actually It is O(l * 2^l)↵
↵
~~~~~↵
def serialize(self, root):↵
"""Encodes a tree to a single string.↵
↵
:type root: TreeNode↵
:rtype: str↵
"""↵
def get_height(node):↵
if not node:↵
return 0↵
return max(get_height(node.left), get_height(node.right)) +1↵
height = get_height(root) ↵
res = []↵
q = deque()↵
emp = "1001"↵
if not root:↵
res.append(emp)↵
return "".join(res)↵
q.appendleft(root) ↵
for l in range(height + 1):↵
len_q = len(q)↵
for x in range(int(pow(2, l))):↵
curr = q.pop()↵
res.append(str(curr.val))↵
if curr.left:↵
q.appendleft(curr.left)↵
else:↵
q.appendleft(TreeNode(1001))↵
if curr.right:↵
q.appendleft(curr.right)↵
else:↵
q.appendleft(TreeNode(1001))↵
res.append("_")↵
res = "".join(res)↵
return res↵
↵
↵
~~~~~↵
I learned it's just like constructing a tree from pre/post-order. but I don't remember how it's done so I'll study it and return with another post!↵
↵
[INTRO]↵
this blog series is the first of many as my attempt to become an expert on code
I'm
↵
this is proof to myself that I can d
[TOPIC] ↵
Serialization of a binary tree:↵
the problem I tried to solve using bfs, having to cover each level where a level is at most 2^n nodes, making the serialization process intensive to say the least↵
Actually It is O(l * 2^l)↵
↵
~~~~~↵
def serialize(self, root):↵
"""Encodes a tree to a single string.↵
↵
:type root: TreeNode↵
:rtype: str↵
"""↵
def get_height(node):↵
if not node:↵
return 0↵
return max(get_height(node.left), get_height(node.right)) +1↵
height = get_height(root) ↵
res = []↵
q = deque()↵
emp = "1001"↵
if not root:↵
res.append(emp)↵
return "".join(res)↵
q.appendleft(root) ↵
for l in range(height + 1):↵
len_q = len(q)↵
for x in range(int(pow(2, l))):↵
curr = q.pop()↵
res.append(str(curr.val))↵
if curr.left:↵
q.appendleft(curr.left)↵
else:↵
q.appendleft(TreeNode(1001))↵
if curr.right:↵
q.appendleft(curr.right)↵
else:↵
q.appendleft(TreeNode(1001))↵
res.append("_")↵
res = "".join(res)↵
return res↵
↵
↵
~~~~~↵
I learned it's just like constructing a tree from pre/post-order. but I don't remember how it's done so I'll study it and return with another post!↵
↵
