本文共 5576 字，大约阅读时间需要 18 分钟。

二叉树的各种遍历，序列化与反序列化

序列化与反序列化：将变成语言中的结构体序列化成JSON字符串，存入缓存或者通过网络发送给远程服务，消费者接受JSON字符串然后进行范徐丽恶化，就可以得到原始数据了。目的是，已某种固定格式组织字符串，使得数据可以独立于编程语言。

序列化：吧结构化的数据“打平”，其实就是在考察二叉树的遍历方式

反序列化，将字符串还原出二叉树

前序遍历

前序遍历框架：

void traverse(TreeNode root){   	if(root == null) return;	//前序遍历的代码	traverse(root.left);	traverse(root.right);}

序列化，需要将一颗二叉树打平成一个字符串

//代表分割符的字符    String SEP = ",";    //代表null空指针的字符    String NULL = "#";    /**     * 主函数，将二叉树序列化为字符串     */    String serialize(TreeNode root){           //用于拼接字符串        StringBuilder sb = new StringBuilder();        serialize(root,sb);        return sb.toString();    }    /**     * 将二叉树打平为字符串     */    void serialize(TreeNode root,StringBuilder sb){           if (root == null){               sb.append(NULL).append(SEP);            return;        }        /**         * 前序遍历         */        sb.append(root.val).append(SEP);        serialize(root.left,sb);        serialize(root.right,sb);    }

反序列化

先确定根节点root，然后根据前序遍历的规则，递归生成左右子树

/**     * 主函数，将字符串反序列化为二叉树结构     * @param data     * @return     */    TreeNode deserialize_pre(String data){           //将字符串转化为列表        LinkedList
   
     nodes = new LinkedList<>();        for (String s : data.split(SEP)) {               nodes.addLast(s);        }        return deserialize(nodes);    }    /**     * 辅助函数，通过nodes列表构造二叉树     * @param nodes     * @return     */    private TreeNode deserialize(LinkedList
    
      nodes) {           if (nodes.isEmpty())            return null;        /**         * 前序遍历         */        //列表最左侧就是根节点        String first = nodes.removeFirst();        if (first.equals(NULL))            return null;        TreeNode root = new TreeNode(Integer.parseInt(first));        root.left = deserialize(nodes);        root.right = deserialize(nodes);        return root;    }
    
   

后序遍历

后序遍历框架

void traverse(TreeNode root){       if(root == null)        return;    traverse(root.left);    traverse(root.right);}

序列化：

String SEP=",";String NULL="#";String serialize+post(TreeNode root){       StringBuilder sb = new StringBuilder();    serialize(root,sb);    return sb.toString();}void serialize(TreeNode root,StringBuilder sb){       if(root == null){           sb.append(NULL).append(SEP);        return;    }    serialize(root.left,sb);    serialize(root.right,sb);    sb.append(root.val).append(SEP);}

反序列化：

从后往前取出列表元素，一定要先构造root.right子树，后构造root.left子树

/**     * 主函数，将字符串反序列化为二叉树结构     * @param data     * @return     */    TreeNode deserialize_post(String data){           //将字符串转化为列表        LinkedList
   
     nodes = new LinkedList<>();        for (String s : data.split(SEP)) {               nodes.addLast(s);        }        return deserialize(nodes);    }    /**     * 辅助函数，通过nodes列表构造二叉树     * @param nodes     * @return     */    private TreeNode deserialize(LinkedList
    
      nodes) {           if (nodes.isEmpty())            return null;        //从后往前取出元素        String last = nodes.removeLast();        if (last.equals(NULL))            return null;        TreeNode root = new TreeNode(Integer.parseInt(last));        root.right = deserialize(nodes);        root.left = deserialize(nodes);        return root;    }
    
   

中序遍历

中序遍历不能反序列化，因为root的值被夹在两颗子树的中间，我们不知道确切的索引位置，无法找到root节点，无法进行反序列化

中序遍历序列化：

void serialize(TreeNode root,StringBuilder sb){       if(root == null){           sb.append(NULL).append(SEP);        return;    }    serialize(root.left,sb);    sb.append(root.val).append(SEP);    serialize(root.right,sb);}

层序遍历

层序遍历框架：

void traverse(TreeNode root){   	if(root == null) return;	//初始化列表，将root加入队列	Queue
   
     q = new LinkedList<>();	q.offer(root);	while(!q.isEmpty()){   		TreeNode cur = q.poll();		        /**        层序遍历代码位置        */        if(cur == null) continue;        System.out.prontlin(cur.val);        q.offer(cur.left);        q.offer(cur.right);	}}
   

序列化：

//代表分割符的字符    String SEP = ",";    //代表null空指针的字符    String NULL = "#";    /**     * 主函数，将二叉树序列化为字符串     */    String serialize_level(TreeNode root){           //用于拼接字符串        StringBuilder sb = new StringBuilder();        //初始化队列，将root加入队列        Queue
   
     q = new LinkedList<>();        q.offer(root);        while (!q.isEmpty()){               TreeNode cur = q.poll();            //层序遍历            if (cur == null){                   sb.append(NULL).append(SEP);                continue;            }            sb.append(cur.val).append(SEP);            q.offer(cur.left);            q.offer(cur.right);        }        return sb.toString();    }
   

反序列化

/**     * 主函数，将字符串反序列化为二叉树结构     * @param data     * @return     */    TreeNode deserialize_level(String data){           if (data.isEmpty())            return null;        String[] nodes = data.split(SEP);        //第一个元素就是root的值        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));        //队列q记录父节点，将root加入队列        Queue
   
     q = new LinkedList<>();        q.offer(root);        for (int i = 1; i < nodes.length ; i++) {               //队列中存的是父节点            TreeNode parent = q.poll();            //父节点对应的左侧子节点的值            String left = nodes[i++];            if (!left.equals(NULL)){                   parent.left = new TreeNode(Integer.parseInt(left));                q.offer(parent.left);            }else {                   parent.left = null;            }            //父节点对应的右侧子节点的值            String right = nodes[i++];            if (!right.equals(NULL)){                   parent.right = new TreeNode(Integer.parseInt(right));                q.offer(parent.right);            }else {                   parent.right = null;            }        }        return root;    }