【面试题61-序列化二叉树】

剑指offer第六十一题。

题目描述

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

解题思路

比较简单的解题思路是：层序遍历二叉树，将这遍历结果组装成字符串，那么序列化就完成了。下面就是根据这个字符串想办法再还原为原来的二叉树。

我的答案

import java.util.LinkedList;
public class Solution {
    String Serialize(TreeNode root) {
        //层序遍历放进StringBuilder中，空的则为#
        LinkedList<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        if(root == null){
            return null;
        }
        queue.push(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.pop();
            if(node != null){
                queue.add(node.left);
                queue.add(node.right);
                sb.append(node.val+",");
            }else{
                sb.append("#,");
            }
        }
        if(sb.length() != 0){
            sb.deleteCharAt(sb.length()-1);
        }
        return sb.toString();
    }
    
    TreeNode Deserialize(String str) {
        TreeNode root = null;
        if(str == null || str.trim().length() == 0){
            return null;
        }
        //解析StringBuilder，拆分为数组
        String[] strChar = str.split(",");
        //新建一个一样长度的TreeNode类型的数组
        TreeNode[] nodeArr = new TreeNode[strChar.length];
        //将不为#的字符都转为TreeNode类型，为#的则默认为Null
        for(int i=0;i<strChar.length;i++){
            if(!strChar[i].equals("#")){
                nodeArr[i] = new TreeNode(Integer.valueOf(strChar[i]));
            }
        }
        //依次遍历，还原二叉树
        for(int i=0,j=1;i<strChar.length&&j<strChar.length;i++){
            if(nodeArr[i] != null){
                nodeArr[i].left = nodeArr[j++];
                nodeArr[i].right = nodeArr[j++];
            }
        }
        return nodeArr[0];
    }
}