剑指Offer-序列化二叉树

墨蓝 2022-04-24 21:40 178阅读 0赞

## 题目描述 ##

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

#### 示例 ####

###### 二叉树序列化 ######

{8,4,#,3,#,2}

###### 反序列化 ######

![二叉树反序列化][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]

> **序列化指的是遍历二叉树为字符串；反序列化指的是依据字符串重新构造成二叉树**。下面两种方法，**使用ArrayList层次遍历是完全符合二叉树层次序列化示例**，即示例输入。而**递归的方法不是**，这题的输入输出要求并不明确，**可能序列化与反序列化函数的结果能互相匹配就能AC**。

解题思路—**使用ArrayList层次遍历**：**序列化时使用ArrayList依次保存树的每一层结点**，若结点为空，则保存"\#,"，最后得到结果\{8,4,\#,3,\#,2,\#,\#,\#,\}。为了**完全匹配示例输入\{8,4,\#,3,\#,2\}，最后要将多余的"\#,"删除**。**反序列化**时，使用",“分割字符串，同样**使用ArrayList依次保存生成的结点**，同时**设置标志位par来记录当前父结点**，**遍历字符串时，每次遍历两个字节**。因为只要**当前父结点存在**，字符串如果没有遍历完，那就**必然有它的左右子结点**（如果左子结点处于字符串最后一位，那么右子结点肯定是null，在序列化时被当作多余的”\#,“删除了），每次**遍历完两个字符后，par++**，直至字符串遍历结束。  
解题思路—**递归**：这个方法**非常简洁**，但是它的**序列化结果并不是常规的层次遍历**，**以示例中的二叉树为例，递归得到的序列化为\{8,4,3,2,\#,\#,\#,\#,\#,\}**。**序列化**使用了**前序遍历**，**从根结点开始保存**，若结点为null，则保存”\#,"。**反序列化**时，也是**前序遍历的思想**，**将序列化结果按顺序放置左右结点**。**虽然递归的结果不符合标准输入，但是序列化与反序列化函数的结果能互相匹配应该就能AC。**

## Java解题—使用ArrayList层次遍历 ##

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    import java.util.ArrayList;
    public class Solution {
        public String Serialize(TreeNode root) {
            if(root==null) return null;
            StringBuilder str = new StringBuilder();
            ArrayList<TreeNode> list = new ArrayList<>();
            list.add(root);
            str.append(root.val+",");
    
            while(!list.isEmpty()){
                TreeNode node = list.get(0);
    
                if(node.left!=null){
                    str.append(node.left.val+",");
                    list.add(node.left);
                }else
                    str.append("#"+",");
    
                if(node.right!=null){
                    str.append(node.right.val+",");
                    list.add(node.right);
                }else
                    str.append("#"+",");
                list.remove(0);
            }
            str.deleteCharAt(str.length()-1);
            for(int i=str.length()-1;i>=0;i--){
                if(str.charAt(i)=='#'){
                    str.deleteCharAt(i);
                    str.deleteCharAt(--i);
                }
                else
                    break;
            }
            return str.toString();
        }
        
        public TreeNode Deserialize(String str) {
           if(str==null)
                return null;
            String[] strs = str.split(",");
            ArrayList<TreeNode> tree = new ArrayList<>();
            tree.add(new TreeNode(Integer.valueOf(strs[0])));
            int par = 0;
            for(int i=1;i<strs.length;i++){
                if(strs[i].equals("#"))
                    tree.get(par).left = null;
                else{
                    tree.get(par).left = new TreeNode(Integer.valueOf(strs[i]));
                    tree.add(tree.get(par).left);
                }
    
                if(++i<strs.length){
                    if(strs[i].equals("#"))
                        tree.get(par).right = null;
                    else{
                        tree.get(par).right = new TreeNode(Integer.valueOf(strs[i]));
                        tree.add(tree.get(par).right);
                    }
                }
                par++;
            }
            return tree.get(0);
        }
    }

## Java解题—递归 ##

public class Solution {
        public int index = -1;
        // 前序遍历
        String Serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            if(root == null){
                sb.append("#,");
                return sb.toString();
            }
            sb.append(root.val);
            sb.append(",");
            sb.append(Serialize(root.left));
            sb.append(Serialize(root.right));
            return sb.toString();
        }
        
        TreeNode Deserialize(String str) {
            String[] strs = str.split(",");
            TreeNode node = null;
            if(!strs[++index].equals("#")){
                node = new TreeNode(Integer.valueOf(strs[index]));
                node.left = Deserialize(str);
                node.right = Deserialize(str);
            }
            return node;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]: /images/20220212/6cdc965577dd4733bc0c4e54885bc771.png