LeetCode - Medium - 449. Serialize and Deserialize BST

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

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/serialize-and-deserialize-bst/][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);
    	}
    }

[https_leetcode.com_problems_serialize-and-deserialize-bst]: https://leetcode.com/problems/serialize-and-deserialize-bst/
[LeetCode - Medium - 1008. Construct Binary Search Tree from Preorder Traversal]: https://blog.csdn.net/u011863024/article/details/118055584