Documentation
¶
Index ¶
Constants ¶
View Source
const (
NullNode = "null" // 空节点
)
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BTreeBfsCodec ¶
type BTreeBfsCodec struct {
}
func (BTreeBfsCodec) Deserialize ¶
func (bfs BTreeBfsCodec) Deserialize(data string) *TreeNode
func (BTreeBfsCodec) Serialize ¶
func (bfs BTreeBfsCodec) Serialize(root *TreeNode) string
type BTreeCodec ¶
BFS解题分析 这道题使用BFS的解题更为简单写，默认BFS时，需要判断当前节点是否有左、右子树 而此时，我们无需判断左右子树，当node为None时添加一个None到队列中即可。 DFS解题分析 在使用DFS时，势必将根节点放在第一个位置，可以方便我们反序列化，所以应该使用前序遍历。 遍历的时候同样注意，如果遇到空节点，需要将为空的节点也记录下来 即当一个子节点的左右节点都是None时，表示它其实是一个叶子节点。 反序列化时，同样通过前序遍历来实现，但注意默认的字符串转化为列表后，我们应该将从左到右遍历才满足条件 Python我们可以反转列表或者使用deque的双端队列 Java我们可以链表来实现 具体BFS、DFS解题如下： ---------------bfs------------ class Codec:
def serialize(self, root):
if not root:
return ""
dq = deque([root])
res = []
while dq:
node = dq.popleft()
if node:
res.append(str(node.val))
dq.append(node.left)
dq.append(node.right)
else:
res.append('None')
return ','.join(res)
def deserialize(self, data):
if not data:
return []
dataList = data.split(',')
root = TreeNode(int(dataList[0]))
dq = deque([root])
i = 1
while dq:
node = dq.popleft()
if dataList[i] != 'None':
node.left = TreeNode(int(dataList[i]))
dq.append(node.left)
i += 1
if dataList[i] != 'None':
node.right = TreeNode(int(dataList[i]))
dq.append(node.right)
i += 1
return root
-------------------DFS解题-------------------------- from collections import deque class Codec:
def serialize(self, root):
if not root:
return 'None'
root.left = self.serialize(root.left)
root.right = self.serialize(root.right)
return f"{root.val},{root.left},{root.right}"
def deserialize(self, data):
dq = deque(data.split(','))
def dfs(li):
val = li.popleft()
if val == "None":
return None
root = TreeNode(int(val))
root.left = dfs(li)
root.right = dfs(li)
return root
return dfs(dq)
type BfsLeetcode ¶
type BfsLeetcode struct {
}
func (*BfsLeetcode) Deserialize ¶
func (b *BfsLeetcode) Deserialize(data string) *TreeNode
func (*BfsLeetcode) Serialize ¶
func (b *BfsLeetcode) Serialize(root *TreeNode) string
Source Files
Click to show internal directories.
Click to hide internal directories.