leetcode449. Serialize and Deserialize BST

Honwhy 發布于2019-08-16 16:58 / 3291人閱讀

摘要：題目要求將二叉搜索樹序列化和反序列化，序列化是指將樹用字符串的形式表示，反序列化是指將字符串形式的樹還原成原來的樣子。假如二叉搜索樹的節點較多，該算法將會占用大量的額外空間。

題目要求

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

將二叉搜索樹序列化和反序列化，序列化是指將樹用字符串的形式表示，反序列化是指將字符串形式的樹還原成原來的樣子。

思路和代碼

對于樹的序列化，可以直接聯想到對樹的遍歷。樹的遍歷包括前序遍歷，中序遍歷，后序遍歷和水平遍歷，并且可知前序遍歷和中序遍歷，或中序遍歷和后序遍歷可以構成一棵唯一的樹。除此以外，因為這是一棵二叉搜索樹，可知該樹的中序遍歷就是所有元素的從小到大的排列。

舉個例子，假如一棵樹的結構如下：

該樹的前序遍歷結果為3,2,1,4，中序遍歷為1,2,3,4。再仔細分析前序遍歷的結果，結合二叉搜索樹可知，比中間節點小的值一定位于左子樹，反之一定位于右子樹，即可以對前序遍歷進行分割3,|2,1,|4。也就是說，我們可以只利用前序遍歷，就可以區分出二叉搜索樹的左子樹和右子樹。
代碼如下：

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }

    public void preorder(TreeNode root, StringBuilder result) {
        if(root != null) {
            result.append(root.val);
            result.append(":");
            preorder(root.left, result);
            preorder(root.right, result);
        }
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data==null || data.isEmpty()) return null;
        String[] preorder = data.split(":");
        String[] inorder = Arrays.copyOf(preorder, preorder.length);
        Arrays.sort(inorder, new Comparator(){

            @Override
            public int compare(String o1, String o2) {
                Integer i1 = Integer.valueOf(o1);
                Integer i2 = Integer.valueOf(o2);
                return i1.compareTo(i2);
            }
            
        });
        
        return build(inorder, preorder, 0, 0, inorder.length);
    }
    
    public TreeNode build(String[] inorder, String[] preorder, int inorderStart, int preorderStart, int length) {
        if(length <= 0) return null;
        TreeNode root = new TreeNode(Integer.valueOf(preorder[preorderStart]));
        for(int i = inorderStart ; i < inorderStart+length ; i++) {
            if(inorder[i].equals(preorder[preorderStart])) {
                root.left = build(inorder, preorder, inorderStart, preorderStart+1, i-inorderStart);
                root.right = build(inorder, preorder, i+1, preorderStart+i-inorderStart+1, inorderStart+length-i-1);
                break;
            }
        }
        
        return root;
    }

這里的代碼是直接使用排序生成了二叉搜索樹的中序遍歷的結果，并利用先序遍歷和中序遍歷構造了一棵二叉搜索樹。假如二叉搜索樹的節點較多，該算法將會占用大量的額外空間。可以只用先序遍歷作為構造樹的輸入，代碼如下：

    public TreeNode deserialize(String data) {
        if (data==null) return null;
        String[] strs = data.split(":");
        Queue q = new LinkedList<>();
        for (String e : strs) {
            q.offer(Integer.parseInt(e));
        }
        return getNode(q);
    }
    
    private TreeNode getNode(Queue q) {
        if (q.isEmpty()) return null;
        TreeNode root = new TreeNode(q.poll());//root (5)
        Queue samllerQueue = new LinkedList<>();
        while (!q.isEmpty() && q.peek() < root.val) {
            samllerQueue.offer(q.poll());
        }
        root.left = getNode(samllerQueue);
        root.right = getNode(q);
        return root;
    }

GPU云服務器云服務器 Deserialize serialize BST serialize_precision

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/74300.html

Serialize and Deserialize Binary Tree & BST

摘要：思路理論上說所有遍歷的方法都可以。但是為了使和的過程都盡量最簡單，是不錯的選擇。用作為分隔符，來表示。復雜度代碼思路這道題和之前不同，一般的樹變成了，而且要求是。還是可以用，還是需要分隔符，但是就不需要保存了。 297. Serialize and Deserialize Binary Tree Serialization is the process of converting a...

eccozhou 2019-08-14 17:11 評論0 收藏0
[LeetCode] 297. Serialize and Deserialize Binary T

Problem Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection li...

MRZYD 2019-08-19 11:13 評論0 收藏0
LeetCode 297. Serialize and Deserialize Binary Tre

摘要：題目大意將二叉樹序列化，返回序列化的，和反序列化還原。解題思路技巧在于將記錄為便于將來判斷。的思想將每一層記錄下來，反序列化時也按照層級遍歷的方法依次設置為上一個里面的元素的左孩子和右孩子。變種，可以要求輸出一個，而不是 LeetCode 297. Serialize and Deserialize Binary Tree 題目大意: 將二叉樹序列化，返回序列化的String，和反序列...

cc17 2019-08-16 13:28 評論0 收藏0
[LeetCode] 428. Serialize and Deserialize N-ary Tr

Problem Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection li...

iamyoung001 2019-08-16 13:30 評論0 收藏0
leetcode297. Serialize and Deserialize Binary Tree

摘要：因此題目中的例子的中序遍歷結果為。但是，標準的中序遍歷并不能使我們將該結果反構造成一棵樹，我們丟失了父節點和子節點之間的關系。這里我們也可以明顯的看出來，中序遍歷需要保存的空值遠遠多于廣度優先遍歷。題目要求 Serialization is the process of converting a data structure or object into a sequence of ...

desdik 2019-08-15 14:30 評論0 收藏0