We love coding - #3
更新於 發佈於 閱讀時間約 4 分鐘
Hi, I'm coding dog!
Q: 給定一個二元樹的根節點，請實現一個函數 serialize(root)，將該樹序列化為一個字符串，以及函數 deserialize(s)，將該字符串反序列化回一棵二元樹。
例如，給定以下節點類別：
class Node:def __init__(self, val, left=None, right=None):self.val = valself.left = leftself.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 = valself.left = leftself.right = rightdef 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 Noneval = nodes.pop(0)node = Node(val)node.left = deserialize_helper(nodes)node.right = deserialize_helper(nodes)return nodedef 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"
這個測試應該通過。
留言0
查看全部
你可能也想看
Google News 追蹤
隨著理財資訊的普及，越來越多台灣人不再將資產侷限於台股，而是將視野拓展到國際市場。特別是美國市場，其豐富的理財選擇，讓不少人開始思考將資金配置於海外市場的可能性。
然而，要參與美國市場並不只是盲目跟隨標的這麼簡單，而是需要策略和方式，尤其對新手而言，除了選股以外還會遇到語言、開戶流程、Ap
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
給定一個輸入陣列，每一個tuple代表節點之間了從屬關係。
請從從屬關係重建整顆二元樹，並且返回整顆二元樹的根結點。
題目敘述
題目會給定一顆二元樹的根結點，
要求我們在指定的層樹d，插入新的一層，節點值為v。
原本的左、右子樹，就成為新的那一層的左子樹、右子樹。
題目的原文敘述
測試範例
Example 1:
Input: root = [4,2,6,3,1,5], val = 1, depth =
這篇文章，會帶著大家複習以前學過的二元搜尋樹(Binary Search Tree)框架，
並且以二分搜尋樹的概念與定義為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
二元搜尋樹(Binary Search Tree)的定義
題目敘述
題目會給定我們一顆二元樹的根結點，要求我們計算這棵樹的好結點Good node有多少個?
好結點Good node的定義:
某個節點v是好結點，假如從Root node根結點 到 結點v沿途的節點值都小於等於節點v的節點值。
如果還是覺得很模糊，看下方的測試範例就可以很清楚了解
題目敘述
題目會給定一棵二元樹的根結點，要求我們找出這棵二元樹最後一層最左邊的值。
題目的原文敘述
測試範例
Example 1:
Input: root = [2,1,3]
Output: 1
Example 2:
Input: root = [1,2,3,4,null,5,6
題目敘述
題目會給我們一棵BST二元搜索樹的根結點root，還有一個指定的目標值key。
要求我們在樹中刪除帶有這個key值的節點，並且返回更新過後二元搜索樹的樹根root。
題目的原文敘述
測試範例
Example 1:
Input: root = [5,3,6,2,4,null,
題目敘述
題目會給我們一棵二元搜索樹的根結點root，還有一個指定的目標值val。
要求我們找出在樹中對應到目標值val的節點，假如找不到，請回傳null( null在Python就是None)。
題目的原文敘述
測試範例
Example 1:
Input: root = [4,2,
題目敘述
題目會給定一顆二元樹的根結點Root node，和這棵樹中的任意兩個節點p, q。
請找出p, q 在這棵二元數裡面的最接近公共祖先節點是誰?
最接近的公共節點: 就是p, q兩個節點從下往上走，第一個交會的節點。
題目的原文敘述
測試範例
Example 1:
Inpu
題目敘述
題目會給定一顆二元樹的根結點Root node，和指定的目標值targetSum。
問我們能不能從二元樹裡面找到一條從根結點到葉子結點的路徑，其路徑上的節點值總和恰好為targetSum?
可以的話，返回True。
無解的話，返回False。
題目的原文敘述
測試範例
E
題目敘述
題目會給我們一顆二元樹的根結點，請我們列出每一層最右邊的節點值，以陣列的形式返回答案。
題目的原文敘述
測試範例
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
每一層最右邊的節點值分別是1, 3,
隨著理財資訊的普及，越來越多台灣人不再將資產侷限於台股，而是將視野拓展到國際市場。特別是美國市場，其豐富的理財選擇，讓不少人開始思考將資金配置於海外市場的可能性。
然而，要參與美國市場並不只是盲目跟隨標的這麼簡單，而是需要策略和方式，尤其對新手而言，除了選股以外還會遇到語言、開戶流程、Ap
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
給定一個輸入陣列，每一個tuple代表節點之間了從屬關係。
請從從屬關係重建整顆二元樹，並且返回整顆二元樹的根結點。
題目敘述
題目會給定一顆二元樹的根結點，
要求我們在指定的層樹d，插入新的一層，節點值為v。
原本的左、右子樹，就成為新的那一層的左子樹、右子樹。
題目的原文敘述
測試範例
Example 1:
Input: root = [4,2,6,3,1,5], val = 1, depth =
這篇文章，會帶著大家複習以前學過的二元搜尋樹(Binary Search Tree)框架，
並且以二分搜尋樹的概念與定義為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
二元搜尋樹(Binary Search Tree)的定義
題目敘述
題目會給定我們一顆二元樹的根結點，要求我們計算這棵樹的好結點Good node有多少個?
好結點Good node的定義:
某個節點v是好結點，假如從Root node根結點 到 結點v沿途的節點值都小於等於節點v的節點值。
如果還是覺得很模糊，看下方的測試範例就可以很清楚了解
題目敘述
題目會給定一棵二元樹的根結點，要求我們找出這棵二元樹最後一層最左邊的值。
題目的原文敘述
測試範例
Example 1:
Input: root = [2,1,3]
Output: 1
Example 2:
Input: root = [1,2,3,4,null,5,6
題目敘述
題目會給我們一棵BST二元搜索樹的根結點root，還有一個指定的目標值key。
要求我們在樹中刪除帶有這個key值的節點，並且返回更新過後二元搜索樹的樹根root。
題目的原文敘述
測試範例
Example 1:
Input: root = [5,3,6,2,4,null,
題目敘述
題目會給我們一棵二元搜索樹的根結點root，還有一個指定的目標值val。
要求我們找出在樹中對應到目標值val的節點，假如找不到，請回傳null( null在Python就是None)。
題目的原文敘述
測試範例
Example 1:
Input: root = [4,2,
題目敘述
題目會給定一顆二元樹的根結點Root node，和這棵樹中的任意兩個節點p, q。
請找出p, q 在這棵二元數裡面的最接近公共祖先節點是誰?
最接近的公共節點: 就是p, q兩個節點從下往上走，第一個交會的節點。
題目的原文敘述
測試範例
Example 1:
Inpu
題目敘述
題目會給定一顆二元樹的根結點Root node，和指定的目標值targetSum。
問我們能不能從二元樹裡面找到一條從根結點到葉子結點的路徑，其路徑上的節點值總和恰好為targetSum?
可以的話，返回True。
無解的話，返回False。
題目的原文敘述
測試範例
E
題目敘述
題目會給我們一顆二元樹的根結點，請我們列出每一層最右邊的節點值，以陣列的形式返回答案。
題目的原文敘述
測試範例
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
每一層最右邊的節點值分別是1, 3,