[剑指offer]面试题第[37]题[Leedcode][JAVA][第297题][二叉树列的序列化与反序列化][递归][BFS]

我就是我 2023-02-18 04:30 6阅读 0赞

#### 【问题描述】\[中等\] ####

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
    
    请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
    
    示例: 
    
    你可以将以下二叉树：
    
        1
       / \
      2   3
         / \
        4   5
    
    序列化为 "[1,2,3,null,null,4,5]"
    提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
    
    说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

#### 【解答思路】 ####

###### 1. 递归 DFS ######

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

public class Codec { 
        public String rserialize(TreeNode root, String str) { 
            if (root == null) { 
                str += "null,";
            } else { 
                str += str.valueOf(root.val) + ",";
                str = rserialize(root.left, str);
                str = rserialize(root.right, str);
            }
            return str;
        }
      
        public String serialize(TreeNode root) { 
            return rserialize(root, "");
        }
      
        public TreeNode rdeserialize(List<String> l) { 
            if (l.get(0).equals("null")) { 
                l.remove(0);
                return null;
            }
      
            TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
            l.remove(0);
            root.left = rdeserialize(l);
            root.right = rdeserialize(l);
        
            return root;
        }
      
        public TreeNode deserialize(String data) { 
            String[] data_array = data.split(",");
            List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
            return rdeserialize(data_list);
        }
    };

###### 2. BFS 层次遍历 ######

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

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

public class Codec { 
        public String serialize(TreeNode root) { 
            if(root == null) return "[]";
            StringBuilder res = new StringBuilder("[");
            Queue<TreeNode> queue = new LinkedList<>() { {  add(root); }};
            while(!queue.isEmpty()) { 
                TreeNode node = queue.poll();
                if(node != null) { 
                    res.append(node.val + ",");
                    queue.add(node.left);
                    queue.add(node.right);
                }
                else res.append("null,");
            }
            res.deleteCharAt(res.length() - 1);
            res.append("]");
            return res.toString();
        }
    
        public TreeNode deserialize(String data) { 
            if(data.equals("[]")) return null;
            String[] vals = data.substring(1, data.length() - 1).split(",");
            TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
            Queue<TreeNode> queue = new LinkedList<>() { {  add(root); }};
            int i = 1;
            while(!queue.isEmpty()) { 
                TreeNode node = queue.poll();
                if(!vals[i].equals("null")) { 
                    node.left = new TreeNode(Integer.parseInt(vals[i]));
                    queue.add(node.left);
                }
                i++;
                if(!vals[i].equals("null")) { 
                    node.right = new TreeNode(Integer.parseInt(vals[i]));
                    queue.add(node.right);
                }
                i++;
            }
            return root;
        }
    }

// Encodes a tree to a single string.
    public String serialize(TreeNode root) { 
        if (root == null) { 
            return "";
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> res = new LinkedList<Integer>();
        queue.offer(root);
        //BFS
        while (!queue.isEmpty()) { 
            TreeNode curNode = queue.poll();
            if (curNode != null) { 
                res.add(curNode.val);
                queue.offer(curNode.left);
                queue.offer(curNode.right);
            } else { 
                res.add(null);
            }
        } 
        return res.toString();
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) { 
        if (data.length() == 0) { 
            return null;
        }
        //将字符串还原为数组
        String[] preStr = data.substring(1, data.length() - 1).split(",");
        Integer[] bfsOrder = new Integer[preStr.length];
        for (int i = 0; i < preStr.length; i++) { 
            if (preStr[i].trim().equals("null")) { 
                bfsOrder[i] = null;
            } else { 
                bfsOrder[i] = Integer.parseInt(preStr[i].trim());
            }
        }
    
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode root = new TreeNode(bfsOrder[0]);
        int cur = 1;//通过 cur 指针依次给节点赋值
        queue.offer(root);
        while (!queue.isEmpty()) {  
            TreeNode curNode = queue.poll();
            if (bfsOrder[cur] != null) { 
                curNode.left = new TreeNode(bfsOrder[cur]);
                queue.add(curNode.left);
            }
            cur++; 
            if (bfsOrder[cur] != null) { 
                curNode.right = new TreeNode(bfsOrder[cur]);
                queue.add(curNode.right);
            }
            cur++;
        }
        return root;
    }

#### 【总结】 ####

###### 1.先序遍历和中序遍历可以唯一的确定一个二叉树，前提是元素必须不一样。其次，如果二叉树的遍历考虑了 null，那么不管什么遍历我们都能把二叉树还原。 ######

###### 2.List用法 ######

1.list中添加，获取，删除元素；  
添加方法是：.add(e)；　　  
获取方法是：.get(index)；　　  
删除方法是：.remove(index)； 按照索引删除；　　  
.remove(Object o)； 按照元素内容删除；  
2.list中是否包含某个元素；  
.contains（Object o）； 返回true或者false  
3.list中根据索引将元素数值改变(替换)；  
注意 .set(index, element); 和 .add(index, element)（添加）; 的不同；  
4.list中查看（判断）元素的索引；　（根据元素索引位置进行的判断）　  
注意：.indexOf（）； 和 lastIndexOf（）（最后一个）的不同；  
5.利用list中索引位置重新生成一个新的list（截取集合）；  
方法： .subList(fromIndex, toIndex)；　　.size() ； 该方法得到list中的元素数的和

###### 3.前中后序遍历变化的是\[中\]的位置，左到右的顺序不改变 ######

*  前序遍历 中左右
 *  中序遍历 左中右
 *  后续遍历 左右中

参考链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/er-cha-shu-de-xu-lie-hua-yu-fan-xu-lie-hua-by-le-2/  
参考链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-55/  
参考链接：链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/mian-shi-ti-37-xu-lie-hua-er-cha-shu-ceng-xu-bian-/

List用法详解：https://blog.csdn.net/Barcon/article/details/82628120

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200616100344355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200616100351522.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200723154915289.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200723154946481.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70