297. Serialize and Deserialize Binary Tree

Question: Serialize and Deserialize Binary Tree
Solution1. DFS

preorder traversal 中 → 左 → 右

DFS → recursive function

樹轉 data

1. 儲存 data 的資料結構：res = list()

2. dfs: def dfs(node):

1. 終止條件：

   如果 node 為 None，代表走到葉端，資料存 “null”
   

   if node == None:

   res.append("null")

1. 遞回條件：

   如果 node 有值，則把值放到 list 中: res.append(node.val)

   繼續往下看 left subtree: dfs(node.left)

   繼續往下看 right subtree: dfs(node.right)

1. 回傳字串資料： return “,”.join(res)

data 建樹

1. data type 從 string 轉 list:

2. 一次讀一筆資料

   給定 1 pointer → i，從頭開始讀: self.i = 0

   每讀一筆， i 往後走一格: i += 1

3. dfs: def build_tree():

   1. 讀取第 i 筆資料: val = data[self.i]

   2. 終止條件：

      如果讀到 “null”，表示該 node 為 None，i += 1
      

      if val == "null":

      self.i += 1

      return None

   3. 遞回條件：

      1. 中: root = TreeNode(val)

         self.i += 1

      2. 左: left subtree: root.left = build_tree()

      3. 右: right subtree: root.right = build_tree()

   4. 回傳 root: return root

4. 回傳建好的樹: return build_tree()

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Codec:

def serialize(self, root):

"""Encodes a tree to a single string.

:type root: TreeNode

:rtype: str

"""

res = list()

def preorder_traversal_dfs(node):

if node == None:

res.append("null")

else:

res.append(str(node.val))

preorder_traversal_dfs(node.left)

preorder_traversal_dfs(node.right)

preorder_traversal_dfs(root)

return ",".join(res)

def deserialize(self, data):

"""Decodes your encoded data to tree.

:type data: str

:rtype: TreeNode

"""

data = data.split(",")

self.i = 0

def preorder_build_tree():

root_val = data[self.i]

if root_val == "null":

self.i += 1

return None

root = TreeNode(int(root_val))

self.i += 1

root.left = preorder_build_tree()

root.right = preorder_build_tree()

return root

return preorder_build_tree()

Solution2 BDS

解決 level by level

樹轉 data

1. 用 queue 存 data: q = deque([root])

2. res = list()

3. 只要 q 裡有 node: while q:

   node = q.popleft()

   1. 存 root 值: res.append(q.val)

   2. 存 root.left 值：

      if node.left:

      res.append(node.left.val)

      q.append(node.left)

      else: res.append(”null”)

   3. 存 root.right 值：

      if node.right:

      res.append(node.right.val)

      q.append(node.right)

      else: res.append(”null”)

4. return “,”.join(res)

data 建樹

1. data = data.split()
2. 讀資料的 pointer: p = 0

def bfs(p):

val = data[p]

if val == "null":

return None

root = TreeNode(data[p])

if p * 2 + 1 < len(data):

root.left = bfs(p * 2 + 1)

if p * 2 + 2 < len(data):

root.right = bfs(p * 2 + 2)

return root

# 留給大家寫XD

Video Solution