剑指OfferJZ61：序列化二叉树-java版

我就是我 2022-10-19 08:07 90阅读 0赞

### 剑指OfferJZ61：序列化二叉树-java版 ###

*   *   *  JZ61:请实现两个函数，分别用来序列化和反序列化二叉树

### JZ61:请实现两个函数，分别用来序列化和反序列化二叉树 ###

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（\#），以 ！ 表示一个结点值的结束（value!）。  
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

假如一棵树共有 2 个结点， 其根结点为 1 ，根结点右子结点为 2 ，没有其他结点。按照上面第一种说法可以序列化为“1,\#,2,\#,\#”，按照上面第二种说法可以序列化为“\{0:1,2:2\}”，按照上面第三种说法可以序列化为“1,2;2,1”，这三种序列化的结果都包含足以构建一棵与原二叉树完全相同的二叉树的信息

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]

需要注意：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]

public class jz61 { 
    
        //序列化 二叉树--》字符串
        public static String Serialize(TreeNode root) { 
            StringBuilder ans = new StringBuilder("[");
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);//队列 [1,2,3,null,null,4,5]
    
            int sum=1;//用来记录队列中当前节点及其后面非空节点的个数（控制当前节点的两个null值要不要添加到字符串中）
            while(!queue.isEmpty() && root!=null){ 
                TreeNode node=queue.poll();//poll移除并返问队列头部的元素,如果队列为空，则返回null
                if(node==null){ 
                    ans.append("null");
                }else { 
                    ans.append(node.val);
                    sum--;
                    if (node.left != null) { 
                        sum++;
                    }
                    if (node.right != null) { 
                        sum++;
                    }
                    queue.add(node.left);
                    queue.add(node.right);
                }
                if(sum!=0){ 
                    ans.append(",");
                }else { 
                    break;
                }
            }
            ans.append("]");
            return ans.toString();
        }
    
        //反序列化 字符串--》二叉树
        public static TreeNode Deserialize(String str) { 
            String s=str.substring(1,str.length()-1);//截取子字符串 如：截取[1,2,3,null,null,4,5]的子字符串1,2,3,null,null,4,5
            if("".equals(s)){ 
                return null;//data="[]"
            }
            String[] a=s.split(",");//把字符串s根据“,”拆成n个部分 1 2 3 null null 4 5
            int index=0;
            Queue<TreeNode> queue=new LinkedList<>();
            TreeNode root=new TreeNode(change(a[index++]));
            queue.add(root);
            while(!queue.isEmpty() && index<a.length){ 
                TreeNode node= queue.poll();
                if(!"null".equals(a[index])){ 
                    node.left=new TreeNode(change(a[index++]));
                    queue.add(node.left);
                }else { 
                    index++;
                }
                if(index<a.length && !"null".equals(a[index])){ 
                    node.right=new TreeNode(change(a[index++]));
                    queue.add(node.right);
                }else { 
                    index++;
                }
            }
            return root;
        }
    
        //将String类型转化为整型
        private static int change(String s) { 
            int res=0;
            int i=0;
            int flag=1;//String有可能是负数，我们用flag做标记
            if(s.charAt(0)=='-'){ //charAt(0)返回指定索引处的字符，‘-’代表负号
                i++;
                flag=-1;
            }
            for(;i<s.length();i++){ 
                res=res*10+s.charAt(i)-'0';
            }
            return res*flag;
        }
    
        public static void main(String[] args) { 
            //测试序列化
            //[1,2,3,null,null,4,5]
            TreeNode root=new TreeNode(1);
            root.left=new TreeNode(2);
            root.right=new TreeNode(3);
            TreeNode temp=root.right;
            temp.left=new TreeNode(4);
            temp.right=new TreeNode(5);
            System.out.println(Serialize(root));
    
            //测试反序列化
            TreeNode newRoot=Deserialize(Serialize(root));
            assert newRoot!=null;
            dfs(newRoot);
        }
    
        //前序遍历 如：1 2 3 4 5
        private static void dfs(TreeNode node) { 
            System.out.println(node.val);
            if(node.left!=null){ 
                dfs(node.left);
            }
            if(node.right!=null){ 
                dfs(node.right);
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][20210710111734891.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20221005/ac73be7c7cc449c99419ed0f009765eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]: /images/20221005/e1fcf5e05c3f4d2290326488ed75043b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]: /images/20221005/6b649aec85f445b4a04f6f444f506a12.png
[20210710111734891.gif_pic_center]: /images/20221005/5d2284f2aaee45f3841aca134d94e9f8.png