Binary Tree serialize and de-serialize

题目描述

解题方法

  1. preorder

Important thing about pre-order:

A node's parent is always output before itself!!!

  1. level order的方法也可以

we may also use level-order traversal to write/read binary tree, works because like pre-order, we see parent before its child nodes.

因为空的都用“#”补上了，所以可以根据当前层Node 的数量来获得当前Node的左右child。

Solution

preorder的方法

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        vals_arr = []
        self.serial_helper(root, vals_arr)
        return " ".join(vals_arr)

    def serial_helper(self, root, vals_arr):
        if not root:
            vals_arr.append("#")
        else:
            vals_arr.append(str(root.val))
            self.serial_helper(root.left, vals_arr)
            self.serial_helper(root.right, vals_arr)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        data = iter(data.split())
        return self.deserial_helper(data)

    def deserial_helper(self, data):
        val = data.next()
        if val == "#":
            return None
        else:
            node = TreeNode(int(val))
            node.left = self.deserial_helper(data)
            node.right = self.deserial_helper(data)
        return node

level order，空缺

Reference