Cześć,
robię zadanie na leetcode, mam stworzyć dwie funkcje, do jednej dostaje drzewo binarne i mam jakoś je zapisać, a do drugiej trafia moja struktura i mam odtworzyć to drzewo binarne.
link do zadania: [https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/995/]
tak wygląda mój kod:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if not root:
return None
data = [root.val]
q = [root]
q_now = []
d_help = []
while q:
for node in q:
if node.left:
q_now.append(node.left)
d_help.append(node.left.val)
else:
d_help.append(None)
if node.right:
q_now.append(node.right)
d_help.append(node.right.val)
else:
d_help.append(None)
data += d_help
d_help = []
q, q_now = q_now, []
print(data)
return data
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data:
return None
def create(index):
if index >= len(data) or data[index] == None:
return None
root = TreeNode(data[index])
root.left = create(index*2+1)
root.right = create(index*2+2)
return root
return create(0)
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
Dla początkowego testu było ok, ale już dla drzewa prezentowanego przez leetcode jako [5,2,3,null,null,2,4,3,1] moj kod zapisywal je jako
[5, 2, 3, None, None, 2, 4, 3, 1, None, None, None, None, None, None]
a zwracał drzewo [5,2,3,null,null,2,4]
(Tak leetcode prezentuje drzewa [https://support.leetcode.com/hc/en-us/articles/360011883654-What-does-1-null-2-3-mean-in-binary-tree-representation-])
Proszę o pomoc :)