We use the canonical index trick for heaps, which map the left and right
children to indexes 2i and 2i+1, respectively (we shift one place to the
right, in order to start indexing at 0).
Since the heap representation is good for full-trees, we would need
exponential space to fulfill it; assuming that we can potentially find thin
trees, we opt to use an sparse representation for the array. We serialize the
list of (index,value) pairs. Actually, the array is represented in memory as
Space complexity is O(n), due both the array representation and the
auxiliary stack we use DFS traversal. Time should be O(n) as well due DFS.
class Codec: def serialize(self, root): arr = dict() if not root: return "" stack = [(root, 0)] while stack: node, i = stack.pop() arr[i] = node.val for child, j in ((node.left, 2 * i + 1), (node.right, 2 * i + 2)): if child: arr[j] = child.val stack.append((child, j)) ser = "" for i, v in arr.iteritems(): ser += ("," if i > 0 else "") + str(i) + ":" + str(v) return ser def deserialize(self, data): if not data: return None parse_pair = lambda p: tuple(map(int, p.split(":"))) arr = dict([parse_pair(p) for p in data.split(",")]) root = TreeNode(arr) stack = [(root, 0)] def getpush_child(j): child = None if j in arr: child = TreeNode(arr[j]) stack.append((child, j)) return child while stack: node, i = stack.pop() node.left = getpush_child(2 * i + 1) node.right = getpush_child(2 * i + 2) return root