signed

QiShunwang

“诚信为本、客户至上”

剑指 Offer 37. 序列化二叉树

2021/6/3 13:17:27   来源:

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

剑指 Offer 37. 序列化二叉树 - 力扣(LeetCode) (leetcode-cn.com)

//序列化:利用队列先进先出的特点存储结点,
//如果取出的当前节点不是null,就把它的值添加到结果字符串,并把左右子节点(不管是否为null)加入队列;如果当前节点为null,就把“null”加入结果字符串
//反序列化:同样利用队列先进先出的特点存储已经构建好的节点
//先构建根节点加入队列,然后每次从队列取出一个节点,从字符串中取两个值,构建出当前节点的左右节点,将不为null的左右节点加入队列
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return null;
        }
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        LinkedList<TreeNode> temp = new LinkedList();
        TreeNode node = null;
        temp.add(root);
        while(temp.size() != 0){
            node = temp.removeFirst();
            if(node == null){
                sb.append("null,");
                
            }else{
                sb.append(node.val);
                sb.append(",");
                temp.add(node.left);
                temp.add(node.right);
            }
            
        }
        sb.delete(sb.length() - 1, sb.length());
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null){
            return null;
        }
        data = data.substring(1,data.length() - 1);
        String[] s = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(s[0]));
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        for(int i = 1; i < s.length; i += 2){
            TreeNode node = list.removeFirst();
           
            if(s[i].equals("null")){
                node.left = null;
            }else{
                TreeNode left = new TreeNode(Integer.valueOf(s[i]));
                node.left = left;
                list.addLast(left);
            }

            if(s[i + 1].equals("null")){
                node.right = null;
            }else {
                TreeNode right = new TreeNode(Integer.valueOf(s[i + 1]));
                node.right = right;
                list.addLast(right);
            }
        }
        return root;
    }

}