变强日记18

主要内容

TCP协议是如何保证传输的可靠性的
算法题：序列化二叉树

TCP协议是如何保证传输的可靠性的

TCP提供了一种面向连接的，可靠的字节流服务。两个使用TCP协议的应用在通信之前必须要先建立TCP连接。
为了保证可靠性，TCP主要依靠以下几种方法：

数据包校验：目的是检测数据在传输过程中的任何变化，如哦检验出包有问题，则丢弃报文段并且不会给响应，这时TCP超时后会进行重发。
对失序数据包重排序：既然TCP报文段作为IP数据报来传输，而IP数据报的到达可能会失序，因此TCP报文段的到达也可能会失序。TCP将对失序数据进行重新排序，然后才交给应用层；
丢弃重复数据：对于重复数据，能够丢弃重复数据；
应答机制：当TCP收到发自TCP连接另一端的数据，它将发送一个确认。这个确认不是立即发送，通常将推迟几分之一秒；
超时重发：当TCP发出一个段后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段；
流量控制：TCP连接的每一方都有固定大小的缓冲空间。TCP的接收端只允许另一端发送接收端缓冲区所能接纳的数据，这可以防止较快主机致使较慢主机的缓冲区溢出，这就是流量控制。TCP使用的流量控制协议是可变大小的滑动窗口协议。

算法题：序列化二叉树

题目：
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

解法：

String Serialize(TreeNode root) {

    // 若根节点为空，返回“#,”
    if(root == null){
        return "#,";
    }
    // 新建StringBudffer，存储节点值
    StringBuffer sb = new StringBuffer(root.val+",");
    // 递归左子树
    sb.append(Serialize(root.left));
    // 递归右子树
    sb.append(Serialize(root.right));
    // 返回StringBuffer的字符串值
    return sb.toString();
}

TreeNode Deserialize(String str) {
    String[] ss = str.split(",");
    // 用字符串数组构建字符串队列
    Queue<String> q = new LinkedList<String>();
    for(int i = 0; i < ss.length; i++){
        q.add(ss[i]);
    }
    // 递归生成二叉树
    return preOrder(q);
}
private TreeNode preOrder(Queue<String> q){
    // “弹出”队列下一个字符串
    String val = q.poll();
    // 如果值为'#'说明是空结点
    if(val.equals("#")){
        return null;
    }
    // 如果值不为'#'，用该值的整型值构建节点
    TreeNode node = new TreeNode(Integer.valueOf(val));
    // 遍历构建节点左子树
    node.left = preOrder(q);
    // 遍历构建节点右子树
    node.right = preOrder(q);
    // 返回节点
    return node;
}