We love coding - #3

更新於 發佈於 閱讀時間約 4 分鐘

Hi, I'm coding dog!

raw-image

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,#,#"。

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

以下是 serializedeserialize 函數的實現:

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"

這個測試應該通過。





留言
avatar-img
留言分享你的想法!
avatar-img
CodingDog的沙龍
1會員
4內容數
Solve a coding interview problem everyday.
CodingDog的沙龍的其他內容
2023/03/08
Hi. I'm coding dog. Let's solve today's coding interview problem. Q: 給定一個整數陣列,請在線性時間和常數空間中找到第一個遺失的正整數。換句話說,找到陣列中不存在的最小正整數。陣列也可以包含重複項和負數。 A: 為了找到給定陣列中不
Thumbnail
2023/03/08
Hi. I'm coding dog. Let's solve today's coding interview problem. Q: 給定一個整數陣列,請在線性時間和常數空間中找到第一個遺失的正整數。換句話說,找到陣列中不存在的最小正整數。陣列也可以包含重複項和負數。 A: 為了找到給定陣列中不
Thumbnail
2023/03/08
Hi, I'm coding dog. We love coding. Here's today's coding interview problem. Q: 給定一個整數陣列,請回傳一個新的陣列,其中新陣列中的每個索引 i 的元素都是原始陣列中除了索引 i 的所有數字的乘積。 例如,如果我們的輸
2023/03/08
Hi, I'm coding dog. We love coding. Here's today's coding interview problem. Q: 給定一個整數陣列,請回傳一個新的陣列,其中新陣列中的每個索引 i 的元素都是原始陣列中除了索引 i 的所有數字的乘積。 例如,如果我們的輸
2023/03/07
Hi, I'm coding dog. We love coding. 以下是今天的編碼面試題目。 Q: 給定一個數字列表和一個數字 k,返回列表中是否有任意兩個數字相加得到 k。例如,給定 [10, 15, 3, 7] 和 k 為 17,返回 true,因為 10 + 7 = 17。
Thumbnail
2023/03/07
Hi, I'm coding dog. We love coding. 以下是今天的編碼面試題目。 Q: 給定一個數字列表和一個數字 k,返回列表中是否有任意兩個數字相加得到 k。例如,給定 [10, 15, 3, 7] 和 k 為 17,返回 true,因為 10 + 7 = 17。
Thumbnail
看更多
你可能也想看
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
題目敘述 題目會給定一顆二元樹的根結點, 要求我們在指定的層樹d,插入新的一層,節點值為v。 原本的左、右子樹,就成為新的那一層的左子樹、右子樹。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,6,3,1,5], val = 1, depth =
Thumbnail
題目敘述 題目會給定一顆二元樹的根結點, 要求我們在指定的層樹d,插入新的一層,節點值為v。 原本的左、右子樹,就成為新的那一層的左子樹、右子樹。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,6,3,1,5], val = 1, depth =
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
Thumbnail
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
Thumbnail
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
Thumbnail
題目敘述 題目會給我們一棵二元搜索樹的根結點root,還有一個指定的目標值val。 要求我們找出在樹中對應到目標值val的節點,假如找不到,請回傳null( null在Python就是None)。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,
Thumbnail
題目敘述 題目會給我們一棵二元搜索樹的根結點root,還有一個指定的目標值val。 要求我們找出在樹中對應到目標值val的節點,假如找不到,請回傳null( null在Python就是None)。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,
Thumbnail
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
Thumbnail
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
Thumbnail
題目會給我們節點總數目n、左子樹的關係陣列、右子樹的關係陣列,要求我們驗證在給定的條件下,能不能構成一顆合法的二元樹。
Thumbnail
題目會給我們節點總數目n、左子樹的關係陣列、右子樹的關係陣列,要求我們驗證在給定的條件下,能不能構成一顆合法的二元樹。
Thumbnail
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
Thumbnail
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
Thumbnail
題目會給我們一顆二元樹的根節點, 要求我們對齊根節點正中央的虛擬分割線,反轉整顆二元樹。
Thumbnail
題目會給我們一顆二元樹的根節點, 要求我們對齊根節點正中央的虛擬分割線,反轉整顆二元樹。
Thumbnail
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
Thumbnail
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
Thumbnail
Hi, I'm coding dog! Q: 給定一個二元樹的根節點,請實現一個函數 serialize(root),將該樹序列化為一個字符串,以及函數 deserialize(s),將該字符串反序列化回一棵二元樹。 例如,給定以下節點類別: 以下測試應該通過: A: 序列化的過程可以通過對樹進行先
Thumbnail
Hi, I'm coding dog! Q: 給定一個二元樹的根節點,請實現一個函數 serialize(root),將該樹序列化為一個字符串,以及函數 deserialize(s),將該字符串反序列化回一棵二元樹。 例如,給定以下節點類別: 以下測試應該通過: A: 序列化的過程可以通過對樹進行先
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News