[数据结构与算法]【LeetCode】序列化二叉树

思路：

递归

我们采用前序遍历的方式构造字符串并恢复树

• 序列化过程

1. 递归函数退出条件是当节点为空，则返回"#“。我们一定要用一个”#"来实现占位的操作，这样才能保证我们的树是唯一的，否则 单独前序遍历出来的字符串是无法恢复成唯一的一棵树的
2. 然后我们递归地返回 当前值+","+递归左子节点+","+递归右子节点

• 反序列化过程

3. 我们引入了一个新的结构queue来储存字符串分割后的前序遍历结果
4. 由于前序遍历，我们首先从queue中取出队首，将其对象化成为一个节点
5. 然后将左子节点值设为递归这个queue的函数返回结果
6. 然后将右子节点值设为递归这个queue的函数返回结果
7. 这正好符合了前序遍历的规则，我们倒着又建立了这棵树

代码实现：

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[] strs = str.split(",");//分割字符串
        //将分割后的字符串入队
        Queue<String> queue = new LinkedList<>();
        for (int i = 0 ; i < strs.length ; i++) {
            queue.offer(strs[i]);
        }
        return res(queue);//依次出队，根据序列化反序列化构建二叉树
    }

    TreeNode res(Queue<String> queue) {
        String pop = queue.poll();//每次从队首读一个节点，序列化的时候用的是前序遍历，所以现在读的顺序也是前序
        if (pop.equals("#")) return null; //读到#说明是空节点
        TreeNode head = new TreeNode(Integer.valueOf(pop));//构建根节点
        head.left = res(queue);//构建左子树
        head.right = res(queue);//构建右子树
        return head;
    }
}

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

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖