Leetcode brush question diary sword finger offer II 048. serialization and deserialization binary tree

Original link （https://leetcode.cn/problems/h54YBf/）

Title Description

Serialization is the operation of converting a data structure or object into consecutive bits , Then the transformed data can be stored in a file or memory , It can also be transmitted to another computer environment through the network , Reconstruct the original data in the opposite way .

Please design an algorithm to realize the serialization and deserialization of binary tree . There's no limit to your sequence / Deserialization algorithm execution logic , It is only necessary to ensure that a binary tree can be serialized into a string and deserialize the string into the original tree structure .

Example 1

Input ：root = [1,2,3,null,null,4,5]
Output ：[1,2,3,null,null,4,5]

Example 2

Input ：root = []
Output ：[]

Example 3

Input ：root = [1]
Output ：[1]

Example 4

Input ：root = [1,2]
Output ：[1,2]

Data constraints

• The number of nodes in the tree is in the range [0, 104] Inside
• -1000 <= Node.val <= 1000

Ideas

For serializing binary trees, the most natural way to think of is which traversal methods of binary trees —— The first sequence traversal , In the sequence traversal , After the sequence traversal , Here we use preorder traversal to construct a string , For each node, add its corresponding number , Use at the same time "null" Filling a binary tree makes it a “ Full binary tree ”, Use... In construction String Of split Function decomposes it into an array of characters , Then use the queue to store each node , Let one node out of the queue every time , Meet for "null" The node of is naturally given to that node null that will do .
Such as Example 1 It will become

Code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Codec {
    

	public String serialize(TreeNode root) {
    
		return serialize(root, "");
	}

	public String serialize(TreeNode root, String str) {
    
		if (root == null) {
    
			str += "null,";

		} else {
    
			String tmp = root.val + ",";
			str += tmp;
			str = serialize(root.left, str);
			str = serialize(root.right, str);
		}
		return str;

	}

	// Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
    
		String[] nodes=data.split(",");
		Queue<String> queue=new LinkedList<>(Arrays.asList(nodes));
		return deserialize(queue);
		
	}
	public TreeNode deserialize(Queue<String> queue) {
    
		String val=queue.poll();
		if(val.equals("null")) {
    
			
			return null;
		}
		TreeNode node=new TreeNode(Integer.parseInt(val));
		
		node.left=deserialize(queue);
		node.right=deserialize(queue);
		return node;
	}
}