[每日一道小算法（四十二）] [二叉树] [递归] 序列化二叉树

红太狼 2023-07-06 08:59 6阅读 0赞

前言：  
树的题基本都可以用递归来解决，递归真的很好用！！！！

### 题目描述 ###

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

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

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

### 题目解析 ###

序列化二叉树我们可以使用中序遍历来进行遍历二叉树，空结点用\#来代替，用","逗号来隔开，并以字符串的形式返回。

反序列化：我们可以根据逗号来分隔数组，然后我们设置一个序号。根据index的值来设置树节点val，如果节点的值为\#，则返回空节点。

### 代码样例 ###

package com.asong.leetcode.TreeSerialize;
    
    
    /** * 序列化二叉树 */
    public class Solution { 
        //以后逗号分隔结点 结点为空则返回"#"
        String Serialize(TreeNode root) { 
            if(root == null)
            { 
                return "#";
            }
            return root.val + "," + Serialize(root.left) + "," + Serialize(root.right);
        }
        int index = -1; //索引标
        //反序列化
        TreeNode Deserialize(String str) { 
            String[] s = str.split(",");
            index++;
            if(index>s.length)
            { 
                return null;
            }
            TreeNode node = null;
            if(!s[index].equals("#"))
            { 
                node = new TreeNode(Integer.parseInt(s[index]));
                node.left = Deserialize(str);
                node.right = Deserialize(str);
            }
            return node;
        }
    
        public static void main(String[] args) { 
    
            TreeNode treeNode1 = new TreeNode(1);
            TreeNode treeNode2 = new TreeNode(2);
            TreeNode treeNode3 = new TreeNode(3);
            TreeNode treeNode4 = new TreeNode(4);
            TreeNode treeNode5 = new TreeNode(5);
            TreeNode treeNode6 = new TreeNode(6);
    
            treeNode1.left = treeNode2;
            treeNode1.right = treeNode3;
    
            treeNode2.left = treeNode4;
            treeNode3.left = treeNode5;
            treeNode3.right = treeNode6;
    
            Solution serializeTree = new Solution();
    
            String str = serializeTree.Serialize(treeNode1);
            System.out.println(str);
            TreeNode treeNode = serializeTree.Deserialize(str);
            System.out.println(treeNode.val);
        }
    }