def deserialize(self, data):
if data == 'null': return None
nodes = data.split(',')
root = TreeNode(nodes[0])
q = collections.deque([root])
i = 0
while q and i < len(nodes) - 2:
cur = q.popleft()
lv = nodes[i + 1]
rv = nodes[i + 2]
i += 2
if lv != 'null':
l = TreeNode(lv)
q.append(l)
cur.left = l
if rv != 'null':
r = TreeNode(rv)
q.append(r)
cur.right = r
return root
这个题目虽然并不是完全二叉树的题目，但是却和完全二叉树很像，有借鉴完全二叉树的地方。
代码
代码支持：JS，Python, Go
JS Code：
const serialize = (root) => {
const queue = [root];
let res = [];
while (queue.length) {
const node = queue.shift();
if (node) {
res.push(node.val);
queue.push(node.left);
queue.push(node.right);
} else {
res.push("#");
}
}
return res.join(",");
};
const deserialize = (data) => {
if (data == "#") return null;
const list = data.split(",");
const root = new TreeNode(list[0]);
const queue = [root];
let cursor = 1;
while (cursor < list.length) {
const node = queue.shift();
const leftVal = list[cursor];
const rightVal = list[cursor + 1];
if (leftVal != "#") {
const leftNode = new TreeNode(leftVal);
node.left = leftNode;
queue.push(leftNode);
}
if (rightVal != "#") {
const rightNode = new TreeNode(rightVal);
node.right = rightNode;
queue.push(rightNode);
}
cursor += 2;
}
return root;
};
Python Code:
# 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):
ans = ''
queue = [root]
while queue:
node = queue.pop(0)
if node:
ans += str(node.val) + ','
queue.append(node.left)
queue.append(node.right)
else:
ans += '#,'
print(ans[:-1])
return ans[:-1]
def deserialize(self, data: str):
if data == '#': return None
nodes = data.split(',')
if not nodes: return None
root = TreeNode(nodes[0])
queue = [root]
# 已经有 root 了，因此从 1 开始
i = 1
while i < len(nodes) - 1:
node = queue.pop(0)
lv = nodes[i]
rv = nodes[i + 1]
i += 2
if lv != '#':
l = TreeNode(lv)
node.left = l
queue.append(l)
if rv != '#':
r = TreeNode(rv)
node.right = r
queue.append(r)
return root
Go Code:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
ans := ""
q := []*TreeNode{root} // queue
var cur *TreeNode
for len(q) > 0 {
cur, q = q[0], q[1:]
if cur != nil {
ans += strconv.Itoa(cur.Val) + ","
q = append(q, cur.Left)
q = append(q, cur.Right)
} else {
ans += "#,"
}
}
return ans[:len(ans)-1]
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
if data == "#" {
return nil
}
a := strings.Split(data, ",")
var s string
s, a = a[0], a[1:]
v, _ := strconv.Atoi(s)
root := &TreeNode{Val: v}
q := []*TreeNode{root} // queue
var cur, newNode *TreeNode
for len(a) > 0 {
cur, q = q[0], q[1:] // pop
s, a = a[0], a[1:] // 左子树
if s != "#" {
v, _ := strconv.Atoi(s)
newNode = &TreeNode{Val: v}
cur.Left = newNode
q = append(q, newNode)
}
if len(a) == 0 {
return root
}
s, a = a[0], a[1:] // 右子树
if s != "#" {
v, _ := strconv.Atoi(s)
newNode = &TreeNode{Val: v}
cur.Right = newNode
q = append(q, newNode)
}
}
return root
}
复杂度分析
时间复杂度：$O(N)$，其中 N 为树的节点数。
空间复杂度：$O(Q)$，其中 Q 为队列长度，最坏的情况是满二叉树，此时和 N 同阶，其中 N 为树的节点总数
