思路

题目分析

1. 题目给出我们一棵树，要求我们实现两个函数
2. 第一个函数要求我们以任意遍历方式返回一个字符串
3. 第二个函数要求我们可以从上一个字符串中重新返回这棵树

• 方法一：递归

  • 我们采用前序遍历的方式构造字符串并恢复树
  • 序列化过程
    • 递归函数退出条件是当节点为空，则返回"#"。我们一定要用一个"#"来实现占位的操作，这样才能保证我们的树是唯一的，否则单独前序遍历出来的字符串是无法恢复成唯一的一棵树的
    • 然后我们递归地返回 当前值+","+递归左子节点+","+递归右子节点
  • 反序列化过程
    • 我们引入了一个新的结构queue来储存字符串分割后的前序遍历结果
    • 由于前序遍历，我们首先从queue中取出队首，将其对象化成为一个节点
    • 然后将左子节点值设为递归这个queue的函数返回结果
    • 然后将右子节点值设为递归这个queue的函数返回结果
    • 这正好符合了前序遍历的规则，我们倒着又建立了这棵树

• 方法二：迭代

  • 我们采用层序遍历的方式迭代
  • 序列化过程
    • 队列中存储一层的节点信息
    • 遍历该层的时候进行对字符串的构造
    • 同时不断地压入下一层的节点信息
    • 最终给返回字符串
  • 反序列化过程
    • 引入一个aux队列来辅助建立树
    • aux队列首先同样拿到一层的节点信息
    • 然后配合队列q的信息进行父子节点对应弹出的操作，也就是说aux弹出一次，q中相应的弹出其对应的父子节点
    • 最终返回建立好的树

方法一：递归

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    String Serialize(TreeNode root) {
        if(root == null) return "#";        // 对所有的空节点也要存储占位符号"#"
        return root.val + "," + Serialize(root.left) + "," + Serialize(root.right);    // 递归前序遍历返回字符串
    }
    TreeNode Deserialize(String str) {
       String[] s = str.split(",");                             // 切分字符串
       Queue<String> q = new LinkedList<String>();
       for(int i = 0; i != s.length; i++) q.offer(s[i]);        // 将分割后的字符串数组顺序入队
       return de(q);                                            // 按照新的递归函数进行返回
    }
    
    TreeNode de(Queue<String> queue) {
        String s = queue.poll();                                // 递归函数每次从队首读出一个元素，因此读出的顺序也是前序
        if(s.equals("#")) return null;                          // 对递归推出条件之一进行处理
        TreeNode head = new TreeNode(Integer.valueOf(s));       // 前序首先建立一个节点
        head.left = de(queue);                                  // 然后递归左右子节点
        head.right = de(queue);
        return head;
    }
    
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，所有的节点都要遍历一遍
• 空间复杂度：$O(n)O(n)$，队列空间装载了所有节点的规模

方法二：迭代

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    String Serialize(TreeNode root) {
        String res = "";
        if(root == null) return "#!";                            // 如果根节点为空，则按照我们的格式要求直接返回"#!"便于我们反序列化处理
        Queue<TreeNode> queue = new LinkedList<TreeNode>();      // 引入队列，准备进行层序遍历建立字符串
        queue.offer(root);                                       // 先压入根节点
        while(!queue.isEmpty()) {                                // 队列不空的前提下循环
            int n = queue.size();                                // 获得该层的节点数量
            while(n > 0) {                                       // 对当前一整层进行处理
                TreeNode p = queue.poll();                       // 取出队首
                if(p != null) {                                  // 队首空和非空的处理不同
                    res = res + p.val + "!";                     // 非空时，用节点值+分隔符续接字符串
                    queue.offer(p.left);                         // 左右子节点入队
                    queue.offer(p.right);
                }
                else res = res + "#!";                           // 队首空，则用#填充并+分隔符续接字符串
                n--;                                             // 更新当前层中还未处理的节点个数
            }
        }
        return res;
    }
    
    TreeNode Deserialize(String str) {
       String[] s = str.split("!");                             // 切分字符串
       if(s[0].equals("#")) return null;                        // 特殊情况直接判断处理
       Queue<String> q = new LinkedList<String>();              // 层序的节点排序结果存储在队列q中
       Queue<TreeNode> aux = new LinkedList<TreeNode>();        // 引入aux辅助队列
       for(int i = 0; i != s.length; i++) q.offer(s[i]);        // 将分割后的字符串数组顺序入队
       String cha_num = q.poll();                               // 首先取出来一个字符
       TreeNode root = new TreeNode(Integer.valueOf(cha_num));  // 将取出来的字符初始化节点对象
       TreeNode head = root;
       aux.offer(root);                                         // aux队列也初始化完成
       
       while(!q.isEmpty()) {                                    // 看我们的q队列是否全部字符处理干净了
           int n = aux.size();                                  // aux存储树的每一层节点，n表示该层的节点数量
           while(n > 0) {
               root = aux.poll();                               // 每次取aux队首开始处理
               if(root != null) {                               // 队首空和非空的处理是不同的
                   String a = q.poll();                         // aux取出q中的元素并对象化后，q中存在字符串元素就是aux中这一层节点对应的下一层左右子节点，
                   String b = q.poll();                         // 每一对取出来的a,b都是可以和aux当前队首完全对应上的
                   TreeNode l = a.equals("#") ? null : new TreeNode(Integer.valueOf(a));    // 判断a是否为#决定是否要建立一个新节点
                   TreeNode r = b.equals("#") ? null : new TreeNode(Integer.valueOf(b));    // 判断b是否为#决定是否要建立一个新节点
                   root.left = l;                               // 当前队首指向刚刚对象化的l子节点
                   root.right = r;                              // 当前队首指向刚刚对象化的r子节点
                   if(l != null) aux.offer(l);                  // 通过判断l是否为空，来控制是否要压入新节点，保证aux中每次取出来的队首节点可以对应上q队列中新元素
                   if(r != null) aux.offer(r);                  // 通过判断r是否为空，来控制是否要压入新节点，保证aux中每次取出来的队首节点可以对应上q队列中新元素
               }
               n--;
           }
       }
       return head;
    }
    

}

复杂度分析

• 时间复杂度：$O(n)O(n)$，所有的节点都要遍历一遍
• 空间复杂度：$O(n)O(n)$，队列空间装载了所有节点的规模