怎样分析python二叉树的序列化与反序列化

你可以将以下二叉树：

1

/ \

2 3

/ \

4 5

序列化为 "[1,2,3,null,null,4,5]"

 1public class Codec {
 2
 3    //把树转化为字符串（使用BFS遍历）
 4    public String serialize(TreeNode root) {
 5        //边界判断，如果为空就返回一个字符串"#"
 6        if (root == null)
 7            return "#";
 8        //创建一个队列
 9        Queue queue = new LinkedList<>();
10        StringBuilder res = new StringBuilder();
11        //把根节点加入到队列中
12        queue.add(root);
13        while (!queue.isEmpty()) {
14            //节点出队
15            TreeNode node = queue.poll();
16            //如果节点为空，添加一个字符"#"作为空的节点
17            if (node == null) {
18                res.append("#,");
19                continue;
20            }
21            //如果节点不为空，把当前节点的值加入到字符串中，
22            //注意节点之间都是以逗号","分隔的，在下面把字符
23            //串还原二叉树的时候也是以逗号","把字符串进行拆分
24            res.append(node.val + ",");
25            //左子节点加入到队列中（左子节点有可能为空）
26            queue.add(node.left);
27            //右子节点加入到队列中（右子节点有可能为空）
28            queue.add(node.right);
29        }
30        return res.toString();
31    }
32
33    //把字符串还原为二叉树
34    public TreeNode deserialize(String data) {
35        //如果是"#"，就表示一个空的节点
36        if (data == "#")
37            return null;
38        Queue queue = new LinkedList<>();
39        //因为上面每个节点之间是以逗号","分隔的，所以这里
40        //也要以逗号","来进行拆分
41        String[] values = data.split(",");
42        //上面使用的是BFS，所以第一个值就是根节点的值，这里创建根节点
43        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
44        queue.add(root);
45        for (int i = 1; i < values.length; i++) {
46            //队列中节点出栈
47            TreeNode parent = queue.poll();
48            //因为在BFS中左右子节点是成对出现的，所以这里挨着的两个值一个是
49            //左子节点的值一个是右子节点的值，当前值如果是"#"就表示这个子节点
50            //是空的，如果不是"#"就表示不是空的
51            if (!"#".equals(values[i])) {
52                TreeNode left = new TreeNode(Integer.parseInt(values[i]));
53                parent.left = left;
54                queue.add(left);
55            }
56            //上面如果不为空就是左子节点的值，这里是右子节点的值，注意这里有个i++，
57            if (!"#".equals(values[++i])) {
58                TreeNode right = new TreeNode(Integer.parseInt(values[i]));
59                parent.right = right;
60                queue.add(right);
61            }
62        }
63        return root;
64    }
65}

 1class Codec {
 2
 3    //把树转化为字符串（使用DFS遍历，也是前序遍历，顺序是：根节点→左子树→右子树）
 4    public String serialize(TreeNode root) {
 5        //边界判断，如果为空就返回一个字符串"#"
 6        if (root == null)
 7            return "#";
 8        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
 9    }
10
11    //把字符串还原为二叉树
12    public TreeNode deserialize(String data) {
13        //把字符串data以逗号","拆分，拆分之后存储到队列中
14        Queue queue = new LinkedList<>(Arrays.asList(data.split(",")));
15        return helper(queue);
16    }
17
18    private TreeNode helper(Queue queue) {
19        //出队
20        String sVal = queue.poll();
21        //如果是"#"表示空节点
22        if ("#".equals(sVal))
23            return null;
24        //否则创建当前节点
25        TreeNode root = new TreeNode(Integer.valueOf(sVal));
26        //分别创建左子树和右子树
27        root.left = helper(queue);
28        root.right = helper(queue);
29        return root;
30    }
31}  

把二叉树转化为字符串很简单，关键是怎么把转化的字符串再还原成原来的二叉树，这里使用BFS和DFS都很容易实现。