二元樹的序列化和反序列化

作者：Grey

原文地址：

部落格園：二元樹的序列化和反序列化

CSDN：二元樹的序列化和反序列化

題目連結見：LeetCode 297. Serialize and Deserialize Binary Tree

主要思路

可以用如下三種方式

第一種方式，先序遍歷生成序列化字串，然後按先序規則再反序列化；

第二種方式，後序遍歷生成序列化字串，然後按後序規則再反序列化；

第三種方式，按層遍歷生成序列化字串，然後按層次規則再反序列化。

注：這裡不能用中序方式序列化和反序列化，因為，如果二元樹是如下兩棵

兩棵樹的中序遍歷結果都是[null,a,a,a,null]，這樣進行反序列化的時候，就無法區分這兩棵樹了。

其次，針對任何一棵二元樹，我們需要將一些空的節點補充完整，比如下述二元樹

其中 b 的左孩子，c 的左孩子，d 的右孩子，都是空節點，我們可以用 null 來表示，但是不能忽略，所以以按層序列化為例，我們將空節點設定為‘#’字元，並用'[]'框住序列化的字串，然後用逗號分隔節點，所以，上述二元樹

按層序列化的結果是[a,b,c,#,d,#,e,f,#]

程式碼如下

// 二元樹按層遍歷經典實現。
    public static String serialize(TreeNode head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            sb.append(node == null ? "#" : String.valueOf(node.val)).append(",");
            if (node != null) {
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        sb.append("]");
        return sb.toString();
    }

反序列化的方式就是把上述字串還原成一個二元樹，使用一個佇列即可，程式碼如下：

    // 按層反序列化
    public static TreeNode deserialize(String data) {
        if ("[]".equals(data)) {
            return null;
        }
        data = data.substring(1, data.length() - 2);
        String[] values = data.split(",");
        TreeNode head = new TreeNode(Integer.valueOf(values[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);
        int size = 1;
        while (!queue.isEmpty() && size < values.length) {
            TreeNode c = queue.poll();
            c.left = "#".equals(values[size]) ? null : new TreeNode(Integer.valueOf(values[size]));
            size++;
            if (size < values.length) {
                c.right = "#".equals(values[size]) ? null : new TreeNode(Integer.valueOf(values[size]));
                size++;
            }
            if (c.left != null) {
                queue.offer(c.left);
            }
            if (c.right != null) {
                queue.offer(c.right);
            }
        }
        return head;
    }

先序序列化/反序列化，後序序列化/反序列化方法類似

// 後序方式序列化 迭代方法
    public static String serialize3(TreeNode head) {
        if (head == null) {
            return "[]";
        }
        // 後序遍歷的結果加入棧（可以用遞迴也可以用迭代）
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(head);
        while (!stack1.isEmpty()) {
            TreeNode c = stack1.pop();
            stack2.push(c);
            if (c != null) {
                stack1.push(c.left);
                stack1.push(c.right);
            }
        }
        // 棧->字串
        StringBuilder sb = new StringBuilder("[");
        while (!stack2.isEmpty()) {
            TreeNode node = stack2.pop();
            sb.append(node == null ? "#" : node.val).append(",");
        }
        sb.append("]");
        return sb.toString();
    }

    // 後序方式反序列化 迭代方式
    public static TreeNode deserialize3(String data) {
        if ("[]".equals(data)) {
            return null;
        }
        String[] values = data.substring(1, data.length() - 2).split(",");
        Stack<String> stack = new Stack<>();
        for (String value : values) {
            stack.push(value);
        }
        return posDerial(stack);
    }

    private static TreeNode posDerial(Stack<String> stack) {
        String s = stack.pop();
        if ("#".equals(s)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(s));
        root.right = posDerial(stack);
        root.left = posDerial(stack);
        return root;
    }

    // 先序方式序列化 迭代做法
    // 頭 左 右
    public static String serialize2(TreeNode head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Stack<TreeNode> queue = new Stack<>();
        queue.push(head);
        while (!queue.isEmpty()) {
            TreeNode c = queue.pop();
            sb.append(c == null ? "#" : c.val).append(",");
            if (c != null) {
                queue.push(c.right);
                queue.push(c.left);
            }
        }
        sb.append("]");
        return sb.toString();
    }

    // 先序反序列化
    public static TreeNode deserialize2(String data) {
        if ("[]".equals(data)) {
            return null;
        }
        String[] values = data.substring(1, data.length() - 2).split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        for (String value : values) {
            queue.offer("#".equals(value) ? null : new TreeNode(Integer.valueOf(value)));
        }
        return preDesrial(queue);
    }

    private static TreeNode preDesrial(Queue<TreeNode> queue) {
        TreeNode node = queue.poll();
        if (node == null) {
            return null;
        }
        node.left = preDesrial(queue);
        node.right = preDesrial(queue);
        return node;
    }

更多

演演算法和資料結構筆記