1. 问题背景

二叉树被记录为文件的过程叫作二叉树的序列化,通过文件内容重建原来二叉树的过程叫作二叉树的反序列化,给定一颗二叉树,请将该二叉树先序序列化和层序序列化。
假设序列化的结果字符串为 str,初始时 str = "",遍历二叉树时,遇到 null 节点,则在 str 的末尾加上 "#!",否则加上"当前的节点值!"。

2. 输入输出

第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch 同理)

输出两行分别表示该二叉树的先序序列化和层序序列化

input
2 1
1 2 0
2 0 0
output
1!2!#!#!#!
1!2!#!#!#!

3. 问题解答

首先定义节点 Node 如下:

public class Node {

    public final int value;

    public Node left;

    public Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}

3.1 反序列化

题目在这里其实有一点模糊,在于题目中并没有给出输入的遍历方式。同样一棵二叉树,用深度优先和广度优先会有不同的表示方式。如果不指定遍历方式的话,就必须加上节点值两两不相同这个限制。另外 input 的第一行其实没有带来额外的信息,解答中没有直接使用第一行输入。

下面的解答是基于深度优先遍历来解答的。


public class Deserializer {

    public Node createTree(String[] args) {
        String[] firstLine = args[1].split(" ");

        return createTree(Integer.parseInt(firstLine[0]), Integer.parseInt(firstLine[1]), Integer.parseInt(firstLine[2]), args, 1);
    }

    private Node createTree(int fatherValue, int leftValue, int rightValue, String[] args, int index) {
        // 创建当前节点
        Node node = new Node(fatherValue);

        if (leftValue != 0) {
            // 如果左子树不空,说明下一条输入是左子树的子树,因此index加1
            String arg = args[++index];
            // 创建当前节点的左子树
            node.left = createTree(leftValue, Integer.parseInt(arg.split(" ")[1]), Integer.parseInt(arg.split(" ")[2]), args, index);
        }

        if (rightValue != 0) {
            String arg = args[++index];
            node.right = createTree(rightValue, Integer.parseInt(arg.split(" ")[1]), Integer.parseInt(arg.split(" ")[2]), args, index);
        }

        return node;
    }
}

相应地,添加了一些单元测试用例:

import org.junit.Assert;
import org.junit.Test;

public class TestDeserializer {

    @Test
    public void testCreateTree0() {
        String[] input = new String[] {
                "2 1",
                "1 2 0",
                "2 0 0"
        };

        Deserializer deserializer = new Deserializer();
        Node tree = deserializer.createTree(input);

        Assert.assertEquals(1, tree.value);
        Assert.assertEquals(2, tree.left.value);
        Assert.assertNull(tree.right);
        Assert.assertNull(tree.left.left);
        Assert.assertNull(tree.left.right);
    }

    @Test
    public void testCreateTree1() {
        String[] input = new String[] {
                "1 1",
                "1 0 0",
        };

        Deserializer deserializer = new Deserializer();
        Node tree = deserializer.createTree(input);

        Assert.assertEquals(1, tree.value);
        Assert.assertNull(tree.left);
        Assert.assertNull(tree.right);
    }

    @Test
    public void testCreateTree2() {
        String[] input = new String[] {
                "1 1",
                "1 2 3",
                "2 3 4",
                "3 0 0",
                "4 0 1",
                "1 0 0",
                "3 0 0",
        };

        Deserializer deserializer = new Deserializer();
        Node tree = deserializer.createTree(input);

        Assert.assertEquals(1, tree.value);
        Assert.assertEquals(2, tree.left.value);
        Assert.assertEquals(3, tree.right.value);
        Assert.assertEquals(3, tree.left.left.value);
        Assert.assertEquals(4, tree.left.right.value);
        Assert.assertEquals(1, tree.left.right.right.value);
    }
}

3.2 序列化

序列化考查的点其实在于深度优先和广度优先遍历,只需要按遍历顺序输出就好。

深度优先的思路关键在于有相同子结构,因此用递归是比较方便的方式。
广度优先是用FIFO 队列来组织节点访问顺序,先访问的先推到队列中,后访问的后推到队列中。

import java.util.LinkedList;

public class Serializer {

    public String depthFirst(Node root) {
        StringBuilder result = new StringBuilder();
        depthFirst(root, result);
        return result.toString();
    }

    private void depthFirst(Node root, StringBuilder result) {

        if (root == null) {
            result.append("#!");
            return;
        }

        // 先序遍历
        result.append(root.value).append("!");

        depthFirst(root.left, result);
        depthFirst(root.right, result);
    }

    public String breadthFirst(Node node) {
        StringBuilder result = new StringBuilder();
        // 用FIFO队列去组织节点访问顺序
        LinkedList<Node> nodeToVisit = new LinkedList<>();

        nodeToVisit.add(node);

        while (!nodeToVisit.isEmpty()) {
            Node n = nodeToVisit.poll();

            if (n == null) {
                result.append("#!");
                continue;
            }
            result.append(n.value).append("!");
            nodeToVisit.offer(n.left);
            nodeToVisit.offer(n.right);
        }

        return result.toString();
    }

}

相应单元测试用例:

import org.junit.Assert;
import org.junit.Test;

public class TestSerializer {

    @Test
    public void testDepthFirst0() {
        Node root = new Node(1);
        root.left = new Node(2);

        Serializer serializer = new Serializer();

        Assert.assertEquals("1!2!#!#!#!", serializer.depthFirst(root));
    }

    @Test
    public void testDepthFirst1() {
        Node root = new Node(1);

        Serializer serializer = new Serializer();

        Assert.assertEquals("1!#!#!", serializer.depthFirst(root));
    }

    @Test
    public void testDepthFirst2() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(3);
        root.left.left.right = new Node(1);
        root.left.right = new Node(4);

        Serializer serializer = new Serializer();

        Assert.assertEquals("1!2!3!#!1!#!#!4!#!#!3!#!#!", serializer.depthFirst(root));
    }

    @Test
    public void testBreadthFirst0() {
        Node root = new Node(1);
        root.left = new Node(2);

        Serializer serializer = new Serializer();

        Assert.assertEquals("1!2!#!#!#!", serializer.breadthFirst(root));
    }

    @Test
    public void testBreadthFirst1() {
        Node root = new Node(1);

        Serializer serializer = new Serializer();

        Assert.assertEquals("1!#!#!", serializer.breadthFirst(root));
    }

    @Test
    public void testBreadthFirst2() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(3);
        root.left.left.right = new Node(1);
        root.left.right = new Node(4);

        Serializer serializer = new Serializer();

        Assert.assertEquals("1!2!3!3!4!#!#!#!1!#!#!#!#!", serializer.breadthFirst(root));
    }
}

4. 总结一下

不论是序列化或反序列化,这个问题主要考察的点就在于二叉树的遍历,了解遍历流程就比较容易解决。

从工程角度来说,输入和输出的方法应该抽象成接口,以便将来可以替换算法,某种程度上可以归到策略模式里。

如果只针对问题的话,还有一些 tricky 的解法。比如我们就限定输入时是采用的深度优先遍历,那么我们在输出的时候,其实可以直接参照输入的顺序,不需要创建树,当然广度优先输出就不能这样操作了。