LC 449. Serialize and Deserialize BST
Problem
449. Serialize and Deserialize BST
Solution in Python
Most tree problems can be solved recursively. This one is the same. A preorder traversal is used here to serialize and deserialize the BST tree. Preorder is the order of “root, left, right”. Since it is a BST, we know that given a list of node values, the first element is the root. For the rest part,
left = [val < root_val for val in rest]
right = [val >root_val for val in rest]
Then we can solve the problem recursively, which is :
suppose we have node_vals, we will have
root_val = node_vals[0]
rest = node_vals[1:]
root_node = TreeNode(root_val)
left_node = [val < root_val for val in rest]
right_node = [val >root_val for val in rest]
root.left, root.right = left_node, right_node
Done.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Codec: def serialize(self, root: TreeNode) -> str:
"""Encodes a tree to a single string.
"""
def helper(node):
if node is None:return []
return [node.val] + helper(node.left) + helper(node.right)
node_vals = helper(root)
return ",".join(str(val) for val in node_vals) def deserialize(self, data: str) -> TreeNode:
"""Decodes your encoded data to tree.
"""
if not data:return None
node_vals = data.split(',')
node_vals = [int(val) for val in node_vals]
def helper(node_vals):
if not node_vals:return None
root = TreeNode(node_vals[0])
left_node = helper([val for val in node_vals[1:] if val < node_vals[0]])
right_node = helper([val for val in node_vals[1:] if val > node_vals[0]])
root.left = left_node
root.right = right_node
return root
return helper(node_vals)# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans
For more binary tree problems see my previous post.
Thanks for reading. Happy coding.
