二叉树的序列化与反序列化

不念不忘少年蓝@ 2024-04-18 17:11 62阅读 0赞

为了方便自己测试二叉树相关的代码，需要根据层序遍历快速反序列化一颗用于测试的二叉树，这样可以很方便的写测试用例。

因此简单梳理一下基于层序遍历的二叉树的序列化问题。

**LintCode地址**：[https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree/description][https_www.lintcode.com_problem_serialize-and-deserialize-binary-tree_description]

**举例说明**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20190910014457858.png]

**序列化过程**

与层次遍历相同的是：元素出现的次序与层序遍历相同；与层序遍历不同的是：增加的`#`，只要是非最后一层的节点，如果孩子为空，就需要用`#`表示。

在序列化的过程中，用`ArrayList`结构来存储层次遍历的`TreeNode`，将每层的节点存储到`ArrayList`当中，用`StringBuilder`来拼接序列化的结果。

`ArrayList`控制了层序遍历的方向: 在`ArrayList上`的指针不断后移，如果指向的节点不为空，将指向节点的左孩子和右孩子放入到`ArrayList`当中。而`StringBuilder`在遍历过程中不断添加节点值或者\#构造结果。注意因为是序列化，当该节点的孩子节点为空，需要在String结果中添加`#`体现。

反序列化过程

字符串处理获取到字符串数组，根据字符串数组构建二叉树。我们可以观测一个非常使用的规律：对于不为\#的节点，所有节点的左右孩子节点都依次排在list当中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70 1]  
所以，我们可以设定父节点指针`index`，设定当前节点指针。当前节点指针构造节点之后，作为左节点或者有节点挂载在`index`指向的父节点上。当`index`的左、右孩子都处理之后则`index`后移，那么可以设置一个`isLeftChild`的标识位，如果当前是`isLeftChild`则当前节点是父节点的左孩子，反之则为右孩子。每次对右孩子处理完之后`index`指针就需要后移。

换句话说，要注意控制父节点指针index的移动时机，还需要确定当前节点是父节点的左孩子还是右孩子。

import org.junit.Test;
    
    import java.util.ArrayList;
    
    /**
     * @author wanglong
     * @brief
     * @date 2019-09-10 08:56
     */
    
     // Definition of TreeNode:
    
    
    
    
    public class SerializeAndDeserializeBinaryTree {
        class TreeNode {
            public int val;
            public TreeNode left, right;
            public TreeNode(int val) {
                this.val = val;
                this.left = this.right = null;
            }
        }
    
        /**
         * This method will be invoked first, you should design your own algorithm
         * to serialize a binary tree which denote by a root node to a string which
         * can be easily deserialized by your own "deserialize" method later.
         */
        public String serialize(TreeNode root) {
            // write your code here
            if(root == null)
                return new String("{}");
            ArrayList<TreeNode> list = new ArrayList<>();
            list.add(root);
            for(int i = 0; i < list.size(); i ++){
                TreeNode curNode = list.get(i);
                if(curNode != null){
                    list.add(curNode.left);
                    list.add(curNode.right);
                }
            }
    
            while(list.get(list.size() - 1) == null)
                list.remove(list.size() - 1);
    
            StringBuilder sb = new StringBuilder("{");
            sb.append(list.get(0).val);
            for(int i = 1; i < list.size(); i ++){
                if(list.get(i) != null){
                    sb.append(",");
                    sb.append(list.get(i).val);
                }else{
                    sb.append(",#");
                }
            }
    
            sb.append("}");
    
            return sb.toString();
        }
    
        /**
         * This method will be invoked second, the argument data is what exactly
         * you serialized at method "serialize", that means the data is not given by
         * system, it's given by your own serialize method. So the format of data is
         * designed by yourself, and deserialize it here as you serialize it in
         * "serialize" method.
         */
        public TreeNode deserialize(String data) {
            // write your code here
            if(data ==null || data.equals("{}") || data.length() == 0)
                return null;
            data = data.substring(1, data.length() - 1);
            String[] strs = data.split(",");
    
            ArrayList<TreeNode> nodeList = new ArrayList<>();
            TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
            nodeList.add(root);
            boolean isLeftChild = true;
            int index = 0;
            for(int i = 1; i < strs.length; i ++){
                if(!strs[i].equals("#")){
                    TreeNode curNode = new TreeNode(Integer.parseInt(strs[i]));
                    if(isLeftChild)
                        nodeList.get(index).left = curNode;
                    else
                        nodeList.get(index).right = curNode;
                    nodeList.add(curNode);
                }
                if(!isLeftChild) //index计数后移（#和非空节点都需要进行）
                    index ++;
                isLeftChild = !isLeftChild; //左右子节点替换（#和非空节点都需要进行）
            }
            return root;
        }
    
    
        @Test
        public void test(){
            //test case
            System.out.println(deserialize(new String("{3,9,20,#,#,15,7}")));
        }
    }

[https_www.lintcode.com_problem_serialize-and-deserialize-binary-tree_description]: https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/286977f5ae8040d4b00a957a8c46fe71.png
[20190910014457858.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1a8e1e5f61d245af8a137cc5e7015503.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f70d4654d9d04c19a5de28ed8fe622b1.png