LeetCode - Medium - 449. Serialize and Deserialize BST-蒲公英云

LeetCode - Medium - 449. Serialize and Deserialize BST

亦凉 2022-10-08 11:08 73阅读 0赞

Topic

Tree

Description

https://leetcode.com/problems/serialize-and-deserialize-bst/

Serialization is 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 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.

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [ 0 , 1 0 4 ] [0, 10^4] [0,104].
0 < = N o d e . v a l < = 1 0 4 0 <= Node.val <= 10^4 0<=Node.val<=104
The input tree is guaranteed to be a binary search tree.

Analysis

由LeetCode - Medium - 1008. Construct Binary Search Tree from Preorder Traversal得到启发。

序列化：用前序遍历根节点。

反序列化：将前序遍历的序列按照BST通常插入法重建BST。

Submission

import java.util.LinkedList;
import com.lun.util.BinaryTree.TreeNode;
public class SerializeAndDeserializeBST { 
    public static class Codec { 
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) { 
            if(root == null) return "";
            LinkedList<TreeNode> stack = new LinkedList<>();
            StringBuilder sb = new StringBuilder();
            stack.push(root);
            while(!stack.isEmpty()) { 
                TreeNode node = stack.pop();
                sb.append(node.val);
                sb.append(',');
                if(node.right != null)
                    stack.push(node.right);
                if(node.left != null)
                    stack.push(node.left);
            }
            return sb.substring(0, sb.length() - 1);
        }
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) { 
            if(data == null || data.strip().isEmpty())
                return null;
            int value = 0;
            TreeNode root = null, p, parent;
            for(int i = 0; i <= data.length(); i++) { 
                if(i == data.length() || data.charAt(i) == ',') { 
                    if(root == null) { 
                        root = new TreeNode(value);
                    }else { 
                        p = root;
                        parent = null;
                        while(p != null) { 
                            parent = p;
                            if(value < p.val) { 
                                p = p.left;
                            }else if(p.val < value){ 
                                p = p.right;
                            }
                        }
                        if(value < parent.val)
                            parent.left = new TreeNode(value);
                        else
                            parent.right = new TreeNode(value);
                    }
                    value = 0;
                }else { 
                    int num = data.charAt(i) - '0';
                    value = value * 10 + num;
                }
            }
            return root;
        }
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.medium.SerializeAndDeserializeBST.Codec;
import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;
public class SerializeAndDeserializeBSTTest { 
    @Test
    public void test() { 
// SerializeAndDeserializeBST sObj = new SerializeAndDeserializeBST();
        TreeNode original = BinaryTree.integers2BinaryTree(2, 1, 3);
        Codec ser = new Codec();
        Codec deser = new Codec();
        String tree = ser.serialize(original);
        assertEquals("2,1,3", tree);
        TreeNode ans = deser.deserialize(tree);
        assertTrue(BinaryTree.equals(ans, original));
        String tree2 = ser.serialize(null);
        assertEquals("", tree2);
        TreeNode ans2 = deser.deserialize(tree2);
        assertNull(ans2);
    }
}