怎樣分析python二叉樹的序列化與反序列化

你可以將以下二叉樹：

    1

   / \

  2   3

     / \

    4   5

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

 1public class Codec {
2
3    //把樹轉(zhuǎn)化為字符串（使用BFS遍歷）
4    public String serialize(TreeNode root) {
5        //邊界判斷，如果為空就返回一個(gè)字符串"#"
6        if (root == null)
7            return "#";
8        //創(chuàng)建一個(gè)隊(duì)列
9        Queue<TreeNode> queue = new LinkedList<>();
10        StringBuilder res = new StringBuilder();
11        //把根節(jié)點(diǎn)加入到隊(duì)列中
12        queue.add(root);
13        while (!queue.isEmpty()) {
14            //節(jié)點(diǎn)出隊(duì)
15            TreeNode node = queue.poll();
16            //如果節(jié)點(diǎn)為空，添加一個(gè)字符"#"作為空的節(jié)點(diǎn)
17            if (node == null) {
18                res.append("#,");
19                continue;
20            }
21            //如果節(jié)點(diǎn)不為空，把當(dāng)前節(jié)點(diǎn)的值加入到字符串中，
22            //注意節(jié)點(diǎn)之間都是以逗號","分隔的，在下面把字符
23            //串還原二叉樹的時(shí)候也是以逗號","把字符串進(jìn)行拆分
24            res.append(node.val + ",");
25            //左子節(jié)點(diǎn)加入到隊(duì)列中（左子節(jié)點(diǎn)有可能為空）
26            queue.add(node.left);
27            //右子節(jié)點(diǎn)加入到隊(duì)列中（右子節(jié)點(diǎn)有可能為空）
28            queue.add(node.right);
29        }
30        return res.toString();
31    }
32
33    //把字符串還原為二叉樹
34    public TreeNode deserialize(String data) {
35        //如果是"#"，就表示一個(gè)空的節(jié)點(diǎn)
36        if (data == "#")
37            return null;
38        Queue<TreeNode> queue = new LinkedList<>();
39        //因?yàn)樯厦婷總€(gè)節(jié)點(diǎn)之間是以逗號","分隔的，所以這里
40        //也要以逗號","來進(jìn)行拆分
41        String[] values = data.split(",");
42        //上面使用的是BFS，所以第一個(gè)值就是根節(jié)點(diǎn)的值，這里創(chuàng)建根節(jié)點(diǎn)
43        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
44        queue.add(root);
45        for (int i = 1; i < values.length; i++) {
46            //隊(duì)列中節(jié)點(diǎn)出棧
47            TreeNode parent = queue.poll();
48            //因?yàn)樵贐FS中左右子節(jié)點(diǎn)是成對出現(xiàn)的，所以這里挨著的兩個(gè)值一個(gè)是
49            //左子節(jié)點(diǎn)的值一個(gè)是右子節(jié)點(diǎn)的值，當(dāng)前值如果是"#"就表示這個(gè)子節(jié)點(diǎn)
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            //上面如果不為空就是左子節(jié)點(diǎn)的值，這里是右子節(jié)點(diǎn)的值，注意這里有個(gè)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    //把樹轉(zhuǎn)化為字符串（使用DFS遍歷，也是前序遍歷，順序是：根節(jié)點(diǎn)→左子樹→右子樹）
4    public String serialize(TreeNode root) {
5        //邊界判斷，如果為空就返回一個(gè)字符串"#"
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以逗號","拆分，拆分之后存儲(chǔ)到隊(duì)列中
14        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
15        return helper(queue);
16    }
17
18    private TreeNode helper(Queue<String> queue) {
19        //出隊(duì)
20        String sVal = queue.poll();
21        //如果是"#"表示空節(jié)點(diǎn)
22        if ("#".equals(sVal))
23            return null;
24        //否則創(chuàng)建當(dāng)前節(jié)點(diǎn)
25        TreeNode root = new TreeNode(Integer.valueOf(sVal));
26        //分別創(chuàng)建左子樹和右子樹
27        root.left = helper(queue);
28        root.right = helper(queue);
29        return root;
30    }
31}