297. Serialize and Deserialize Binary Tree 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 tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. Example: You may serialize the following tree:
1 / \ 2 3 / \ 4 5as"[1,2,3,null,null,4,5]" Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
前序遍历，序列化时将树变成一个字符串，每个节点的值用一个分隔符“，”隔开，null节点用“NN”表示。 反序列化时用递归的方式处理这个字符串。
TC: O(n), SC: O(n)
public class Codec { private static final String SPLITER = ","; private static final String NN = "N"; // Encodes a tree to a single string. public String serialize(TreeNode root) { // TODO StringBuilder builder = new StringBuilder(); serialHelper(root, builder); return builder.toString(); } private void serialHelper(TreeNode root, StringBuilder builder) { if (root == null) { builder.append(NN).append(SPLITER); return; } builder.append(root.val).append(SPLITER); serialHelper(root.left, builder); serialHelper(root.right, builder); } private int idx; // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] array = data.split(SPLITER); return deserialHelper(array); } private TreeNode deserialHelper(String[] array) { if (NN.equals(array[idx])) { idx++; return null; } TreeNode node = new TreeNode(Integer.parseInt(array[idx++])); node.left = deserialHelper(array); node.right = deserialHelper(array); return node; } }449. Serialize and Deserialize BST 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.
其实之前普通二叉树的算法可以完全解决这个问题，但是我们希望利用二叉树的性质。所以这里用了中序遍历，用最小值最大值的边界来区分节点的位置，这样就不用再存null节点，比之前的算法节省了一些空间。 TC: O(n), SC: O(n)
public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); serializeTree(root, sb); if(sb.length() == 0) return ""; sb.setLength(sb.length() - 1); return sb.toString(); } private void serializeTree(TreeNode root, StringBuilder sb) { if(root == null) return;; sb.append(root.val).append(','); serializeTree(root.left, sb); serializeTree(root.right, sb); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data.length() == 0) return null; String[] dataArr = data.split(","); return deserializeTree(dataArr, new int[]{0}, Integer.MIN_VALUE, Integer.MAX_VALUE); } private TreeNode deserializeTree(String[] dataArr, int[] level, int min, int max) { if(level[0] >= dataArr.length || level[0] < 0) return null; int val = Integer.valueOf(dataArr[level[0]]); if(val > max || val < min) return null; TreeNode root = new TreeNode(val); level[0]++; root.left = deserializeTree(dataArr, level, min, val); root.right = deserializeTree(dataArr, level, val, max); return root; } }428. Serialize and Deserialize N-ary Tree 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 an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example you may serialize the following 3-ary tree as [1 [3[5 6] 2 4]]. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: N is in the range of [1, 1000] Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
题目大意 这道题就是把二叉树换成多叉树进行序列化和反序列化 解题思路 大体思路与之前相同就是在遍历子节点的时候，子节点是存在一个list里的，所以字符串里面除了存每个节点的值外，还需要存父节点的子节点有几个，以便在反序列化的时候知道子节点的起始点。 复杂度 TC: O(n), SC:O(n)
class Codec { // Encodes a tree to a single string. public String serialize(Node root) { List<String> list=new LinkedList<>(); serializeHelper(root,list); return String.join(",",list); } private void serializeHelper(Node root, List<String> list){ if(root==null){ return; }else{ list.add(String.valueOf(root.val)); list.add(String.valueOf(root.children.size())); for(Node child:root.children){ serializeHelper(child,list); } } } // Decodes your encoded data to tree. public Node deserialize(String data) { if(data.isEmpty()) return null; String[] ss=data.split(","); Queue<String> q=new LinkedList<>(Arrays.asList(ss)); return deserializeHelper(q); } private Node deserializeHelper(Queue<String> q){ Node root=new Node(); root.val=Integer.parseInt(q.poll()); int size=Integer.parseInt(q.poll()); root.children=new ArrayList<Node>(size); for(int i=0;i<size;i++){ root.children.add(deserializeHelper(q)); } return root; } }331. Verify Preorder Serialization of a Binary Tree One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.
_9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # #For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,3”.
Example 1:
Input: “9,3,4,#,#,1,#,#,2,#,6,#,#” Output: true Example 2:
Input: “1,#” Output: false Example 3:
Input: “9,#,#,1” Output: false
题目大意 给以个用前序遍历进行序列化的字符串，检查这个字符串是否是正确的序列化的。 解题思路 根据前序遍历序列化的特点，字符串首先加入的是父节点的值，之后分别是左节点，右节点，如果有null节点就用“#”表示，遇到任何违反这个规则的情况就返回false。 第一种方法是使用栈，每当我们发现一个正确的序列后就把这个序列包含的子节点都出栈，然后入栈一个“#”，代表这是一个正确的子树序列。 第二种方法是用指针，就是遇到非“#”的，指针加1，否则指针减一。当遍历完所有节点后，结果如果为0，则是一个正确的序列。 复杂度 TC: O(n) SC: O(n)
//第一种方法 public boolean isValidSerialization(String preorder) { if (preorder == null || preorder.length() == 0){ return true; } String[] ss = preorder.trim().split(","); Deque<String> stk = new ArrayDeque<>(); for (String s: ss){ while (!stk.isEmpty() && s.equals("#") && stk.peek().equals("#")){ stk.pop(); if (stk.isEmpty()) return false; stk.pop(); } stk.push(s); } return stk.size() == 1 && stk.peek().equals("#"); } //第二种方法 public boolean isValidSerialization(String preorder) { String[] s = preorder.split(","); int dlt = 1; for(String ss : s){ if(dlt <= 0) return false; if(!ss.equals("#")) dlt++; else dlt--; } return dlt == 0; } `