297. 二叉树的序列化与反序列化

困难设计先序遍历 + 空节点标记力扣原题 ↗

题目描述

序列化是把数据结构变成一串可以保存或传输的数据，反序列化则是按相反的过程把它恢复回来。

请为二叉树设计一个 Codec 类：serialize(root) 把一棵二叉树编码成字符串，deserialize(data) 把这个字符串还原成树并返回根节点。

编码格式和具体做法都由你决定，只要求先序列化再反序列化之后，得到的树与原树结构相同、每个节点的值也相同。

示例中的树都用层序数组表示，空位记为 null，输出是经过编码再解码后得到的树。你的字符串不必采用这种格式。

示例 1

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

解释：编码再解码后，得到的树和原树一样。

示例 2

输入：root = []
输出：[]

解释：空树编码再解码，仍是空树。

数据范围

节点个数在 [0, 10^4] 之间。
-1000 <= Node.val <= 1000

解题思路：先序遍历 + 空节点标记

序列化：前序遍历，遇到节点写出它的值，遇到空子树写出 "#"。这样每个空位都留下了记号，树形就被完整记录。反序列化：按同样的前序顺序逐个读取 token。读到 "#" 返回 None；读到数字就建节点，再递归读取左子树和右子树。

为什么正确

每次调用 build() 恰好消费一棵完整子树（含空位记号）对应的连续 token，因此左子树读完后，下一个 token 一定属于右子树。

复杂度分析

两个方向都是时间 O(n)，空间 O(n)（字符串长度约 2n+1，递归深度为树高）。

易错点

必须为空子树留下记号。只记录节点值的前序序列无法区分 [1,2] 和 [1,null,2]。另外节点值可能是负数或多位数，token 之间要用分隔符，不能逐字符读取。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Codec:
    def serialize(self, root):
        out = []
        def dfs(node):
            if not node:
                out.append('#')
                return
            out.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(out)

    def deserialize(self, data):
        vals = iter(data.split(','))
        def build():
            v = next(vals)
            if v == '#':
                return None
            node = TreeNode(int(v))
            node.left = build()
            node.right = build()
            return node
        return build()

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder out = new StringBuilder();
        dfs(root, out);
        return out.toString();
    }

    private void dfs(TreeNode node, StringBuilder out) {
        if (out.length() > 0) {
            out.append(',');
        }
        if (node == null) {
            out.append('#');
            return;
        }
        out.append(node.val);
        dfs(node.left, out);
        dfs(node.right, out);
    }

    private String[] vals;
    private int pos;

    public TreeNode deserialize(String data) {
        vals = data.split(",");
        pos = 0;
        return build();
    }

    private TreeNode build() {
        String v = vals[pos++];
        if (v.equals("#")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(v));
        node.left = build();
        node.right = build();
        return node;
    }
}

class Codec {
public:
    string serialize(TreeNode* root) {
        string out;
        dfs(root, out);
        return out;
    }

    void dfs(TreeNode* node, string& out) {
        if (!out.empty()) {
            out += ',';
        }
        if (!node) {
            out += '#';
            return;
        }
        out += to_string(node->val);
        dfs(node->left, out);
        dfs(node->right, out);
    }

    TreeNode* deserialize(string data) {
        int pos = 0;
        return build(data, pos);
    }

    TreeNode* build(const string& data, int& pos) {
        size_t end = data.find(',', pos);
        if (end == string::npos) {
            end = data.size();
        }
        string v = data.substr(pos, end - pos);
        pos = end + 1;
        if (v == "#") {
            return nullptr;
        }
        TreeNode* node = new TreeNode(stoi(v));
        node->left = build(data, pos);
        node->right = build(data, pos);
        return node;
    }
};

type Codec struct {
}

func Constructor() Codec {
	return Codec{}
}

func (this *Codec) serialize(root *TreeNode) string {
	out := []string{}
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			out = append(out, "#")
			return
		}
		out = append(out, strconv.Itoa(node.Val))
		dfs(node.Left)
		dfs(node.Right)
	}
	dfs(root)
	return strings.Join(out, ",")
}

func (this *Codec) deserialize(data string) *TreeNode {
	vals := strings.Split(data, ",")
	pos := 0
	var build func() *TreeNode
	build = func() *TreeNode {
		v := vals[pos]
		pos++
		if v == "#" {
			return nil
		}
		x, _ := strconv.Atoi(v)
		node := &TreeNode{Val: x}
		node.Left = build()
		node.Right = build()
		return node
	}
	return build()
}

var serialize = function(root) {
    const out = [];
    const dfs = (node) => {
        if (!node) {
            out.push('#');
            return;
        }
        out.push(String(node.val));
        dfs(node.left);
        dfs(node.right);
    };
    dfs(root);
    return out.join(',');
};

var deserialize = function(data) {
    const vals = data.split(',');
    let pos = 0;
    const build = () => {
        const v = vals[pos++];
        if (v === '#') {
            return null;
        }
        const node = new TreeNode(Number(v));
        node.left = build();
        node.right = build();
        return node;
    };
    return build();
};

function serialize(root: TreeNode | null): string {
    const out: string[] = [];
    const dfs = (node: TreeNode | null): void => {
        if (!node) {
            out.push('#');
            return;
        }
        out.push(String(node.val));
        dfs(node.left);
        dfs(node.right);
    };
    dfs(root);
    return out.join(',');
}

function deserialize(data: string): TreeNode | null {
    const vals = data.split(',');
    let pos = 0;
    const build = (): TreeNode | null => {
        const v = vals[pos++];
        if (v === '#') {
            return null;
        }
        const node = new TreeNode(Number(v));
        node.left = build();
        node.right = build();
        return node;
    };
    return build();
}

载入编辑器，自己跑一遍 →

其他解法

两种方法都记录空节点，因此单一遍历序列就能唯一确定树。先序递归的序列化和反序列化结构对称、代码短；层序用队列迭代，输出与力扣的树输入格式一致。

解法 2：层序遍历（BFS）时间 O(n)，空间 O(n)

序列化时按层遍历：空节点记为 '#'，非空节点记录值并把左右孩子入队。反序列化时用第一个值建根入队，每取出一个节点就从序列中顺序读两个值作为它的左右孩子，非空的孩子再入队。

格式和力扣自带的数组表示一致，直观易读，且不用递归，深链树不会栈溢出。反序列化要同时维护队列和读取指针，比先序递归略繁琐。

from collections import deque

class Codec:
    def serialize(self, root):
        out = []
        q = deque([root])
        while q:
            node = q.popleft()
            if not node:
                out.append('#')
                continue
            out.append(str(node.val))
            q.append(node.left)
            q.append(node.right)
        return ','.join(out)

    def deserialize(self, data):
        vals = data.split(',')
        if vals[0] == '#':
            return None
        root = TreeNode(int(vals[0]))
        q = deque([root])
        i = 1
        while q:
            node = q.popleft()
            if vals[i] != '#':
                node.left = TreeNode(int(vals[i]))
                q.append(node.left)
            if vals[i + 1] != '#':
                node.right = TreeNode(int(vals[i + 1]))
                q.append(node.right)
            i += 2
        return root

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder out = new StringBuilder();
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (out.length() > 0) out.append(',');
            if (node == null) {
                out.append('#');
                continue;
            }
            out.append(node.val);
            q.offer(node.left);
            q.offer(node.right);
        }
        return out.toString();
    }

    public TreeNode deserialize(String data) {
        String[] vals = data.split(",");
        if (vals[0].equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        int i = 1;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (!vals[i].equals("#")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                q.offer(node.left);
            }
            if (!vals[i + 1].equals("#")) {
                node.right = new TreeNode(Integer.parseInt(vals[i + 1]));
                q.offer(node.right);
            }
            i += 2;
        }
        return root;
    }
}

class Codec {
public:
    string serialize(TreeNode* root) {
        string out;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (!out.empty()) out += ',';
            if (!node) {
                out += '#';
                continue;
            }
            out += to_string(node->val);
            q.push(node->left);
            q.push(node->right);
        }
        return out;
    }

    TreeNode* deserialize(string data) {
        vector<string> vals;
        stringstream ss(data);
        string tok;
        while (getline(ss, tok, ',')) vals.push_back(tok);
        if (vals[0] == "#") return nullptr;
        TreeNode* root = new TreeNode(stoi(vals[0]));
        queue<TreeNode*> q;
        q.push(root);
        int i = 1;
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (vals[i] != "#") {
                node->left = new TreeNode(stoi(vals[i]));
                q.push(node->left);
            }
            if (vals[i + 1] != "#") {
                node->right = new TreeNode(stoi(vals[i + 1]));
                q.push(node->right);
            }
            i += 2;
        }
        return root;
    }
};

type Codec struct {
}

func Constructor() Codec {
	return Codec{}
}

func (this *Codec) serialize(root *TreeNode) string {
	out := []string{}
	q := []*TreeNode{root}
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		if node == nil {
			out = append(out, "#")
			continue
		}
		out = append(out, strconv.Itoa(node.Val))
		q = append(q, node.Left, node.Right)
	}
	return strings.Join(out, ",")
}

func (this *Codec) deserialize(data string) *TreeNode {
	vals := strings.Split(data, ",")
	if vals[0] == "#" {
		return nil
	}
	newNode := func(s string) *TreeNode {
		x, _ := strconv.Atoi(s)
		return &TreeNode{Val: x}
	}
	root := newNode(vals[0])
	q := []*TreeNode{root}
	i := 1
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		if vals[i] != "#" {
			node.Left = newNode(vals[i])
			q = append(q, node.Left)
		}
		if vals[i+1] != "#" {
			node.Right = newNode(vals[i+1])
			q = append(q, node.Right)
		}
		i += 2
	}
	return root
}

var serialize = function(root) {
    const out = [];
    const q = [root];
    for (let h = 0; h < q.length; h++) {
        const node = q[h];
        if (!node) {
            out.push('#');
            continue;
        }
        out.push(String(node.val));
        q.push(node.left, node.right);
    }
    return out.join(',');
};

var deserialize = function(data) {
    const vals = data.split(',');
    if (vals[0] === '#') return null;
    const root = new TreeNode(Number(vals[0]));
    const q = [root];
    let i = 1;
    for (let h = 0; h < q.length; h++) {
        const node = q[h];
        if (vals[i] !== '#') {
            node.left = new TreeNode(Number(vals[i]));
            q.push(node.left);
        }
        if (vals[i + 1] !== '#') {
            node.right = new TreeNode(Number(vals[i + 1]));
            q.push(node.right);
        }
        i += 2;
    }
    return root;
};

function serialize(root: TreeNode | null): string {
    const out: string[] = [];
    const q: (TreeNode | null)[] = [root];
    for (let h = 0; h < q.length; h++) {
        const node = q[h];
        if (!node) {
            out.push('#');
            continue;
        }
        out.push(String(node.val));
        q.push(node.left, node.right);
    }
    return out.join(',');
}

function deserialize(data: string): TreeNode | null {
    const vals = data.split(',');
    if (vals[0] === '#') return null;
    const root = new TreeNode(Number(vals[0]));
    const q: TreeNode[] = [root];
    let i = 1;
    for (let h = 0; h < q.length; h++) {
        const node = q[h];
        if (vals[i] !== '#') {
            node.left = new TreeNode(Number(vals[i]));
            q.push(node.left);
        }
        if (vals[i + 1] !== '#') {
            node.right = new TreeNode(Number(vals[i + 1]));
            q.push(node.right);
        }
        i += 2;
    }
    return root;
}

设计专题的其他题目

查看设计全部题目 →