2023-03-08|閱讀時間 ‧ 約 4 分鐘

We love coding - #3

Hi, I'm coding dog!

Q: 給定一個二元樹的根節點，請實現一個函數 serialize(root)，將該樹序列化為一個字符串，以及函數 deserialize(s)，將該字符串反序列化回一棵二元樹。

例如，給定以下節點類別：

class Node:

    def __init__(self, val, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

以下測試應該通過：

node = Node("root", Node("left", Node("left.left")), Node("right"))

assert deserialize(serialize(node)).left.left.val == "left.left"

A: 序列化的過程可以通過對樹進行先序遍歷來實現，並將每個節點表示為一個字符串，其格式為 "val,left_subtree,right_subtree"。我們可以使用一個特殊字符 "#" 來表示空節點。例如，上面的樹可以序列化為字符串 "root,left,left.left,#,#,#,right,#,#"。

反序列化的過程可以通過遞歸來實現。我們首先將輸入字符串拆分為一個節點值列表，然後使用第一個值創建一個新節點，並使用其餘值遞歸構建其左右子樹。為了跟蹤輸入列表中的當前位置，我們可以使用一個指針在遞歸中傳遞。

以下是 serialize 和 deserialize 函數的實現：

class Node:

    def __init__(self, val, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

def serialize(root):

    if not root:

        return "#"

    left_serialized = serialize(root.left)

    right_serialized = serialize(root.right)

    return f"{root.val},{left_serialized},{right_serialized}"

def deserialize_helper(nodes):

    if nodes[0] == "#":

        nodes.pop(0)

        return None

    val = nodes.pop(0)

    node = Node(val)

    node.left = deserialize_helper(nodes)

    node.right = deserialize_helper(nodes)

    return node

def deserialize(s):

    nodes = s.split(",")

    root = deserialize_helper(nodes)

    return root

我們可以使用提供的示例進行測試：

node = Node("root", Node("left", Node("left.left")), Node("right"))

assert deserialize(serialize(node)).left.left.val == "left.left"

這個測試應該通過。

分享至

成為作者繼續創作的動力吧！

We Love Coding

追蹤

We love coding - #3

作者的相關文章

你可能也想看

發表回應