题目描述

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

解题思路

  1. 对于序列化:使用前序遍历,递归的将二叉树的值转化为字符,并且在每次二叉树的结点不为空时,在转化val所得的字符之后添加一个’,’作为分割; 对于空节点则以 ‘#,’ 代替。
  2. 对于反序列化:将字符串按照“,”进行分割,插入到队列中,然后依次从队列中取出字符建立节点,递归创建一个二叉树。

参考代码

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

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    String Serialize(TreeNode root) {
        if(root == null){
            return "#,";
        }
        StringBuffer res = new StringBuffer(root.val + ",");
        res.append(Serialize(root.left));
        res.append(Serialize(root.right));
        return res.toString();
    }
    TreeNode Deserialize(String str) {
        String [] res = str.split(",");
        Queue<String> queue = new LinkedList<String>();
        for(int i = 0; i < res.length; i++){
            queue.offer(res[i]);
        }
        return pre(queue);
    }
    TreeNode pre(Queue<String> queue){
        String val = queue.poll();
        if(val.equals("#"))
            return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = pre(queue);
        node.right = pre(queue);
        return node;
    }
}

互联网校招面试必备——Redis

Redis有哪些数据结构? 字符串String、字典Hash、列表List、集合Set、有序集合SortedSet。 如果你是Redis中高级用户,还需要加上下面几种数据结构HyperLogLog...

阅读全文

互联网校招面试必备——数据库

DDL(Data Definition Language)数据库定义语言 CREATE、ALTER、DROP、TRUNCATE、COMMENT、RENAME DML(Data Manipulation Language)数据操纵语言 SELECT、...

阅读全文

一文搞定BAT面试——Java 集合类

1. Iterator接口 Iterator接口,这是一个用于遍历集合中元素的接口,主要包含hashNext(),next(),remove()三种方法。它的一个子接口LinkedIterator在它的基...

阅读全文