序列化二叉树（37）.md

1. 问题描述

实现2个函数，分别用于：序列化 & 反序列化 二叉树

a. 序列化：将 二叉树 转换为 字符串 b. 反序列化：根据 字符串 重新构造成 二叉树

---

2. 考察点

• 二叉树的遍历算法

前序、中序、后序遍历

• 分析复杂问题的能力 序列化二叉树 = 序列化 根节点 + 左子树节点 + 右子树节点

---

3. 解题思路

---

4. 算法示意图

---

5. 算法实现

• 具体请看注释

public class Exam_37 {

    /**
     * 节点结构
     */
    public static class TreeNode {
        int val;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 序列化：二叉树转换成字符串
     * 核心思想：采用 递归 实现前序遍历
     */

    public static String Serialize(TreeNode root) {

        StringBuilder sb = new StringBuilder();

        // 检查输入数据的合法性
        if(root == null){
            sb.append("#,"); // 遍历时当遇到空指针时，则采用 特殊字符（如$）代替
            return sb.toString();

        }

        // 根据 前序遍历的顺序 序列化二叉树
        sb.append(root.val + ",");// 1. 序列化根节点
        sb.append(Serialize(root.left));// 2.  序列化左子树
        sb.append(Serialize(root.right)); // 3.  序列化右子树
        return sb.toString();

        }

    /**
     * 反序列化
     * 核心思想：拆分分3步反序列化：反序列化根节点、左子树、右子树
     */

    static int index = -1;   // 当前反序列化节点的下标
    private static TreeNode Deserialize(String str) {

        index++; // 每次递归时记录下当前反序列化节点的下标

        String[] strr = str.split(",");
        TreeNode node = null;

        if(!strr[index].equals("#")){
            node = new TreeNode(Integer.valueOf(strr[index])); // 1. 反序列化根节点，即读取到的第1个数字
            node.left = Deserialize(str); // 2. 反序列化左子树
            node.right = Deserialize(str);// 3. 反序列化右子树
        }

        return node;

        }

    /**
     * 测试用例
     */
    public static void main(String[] args) {
        // 功能测试
        //            1
        //          /   \
        //         2     3
        //        /     / \
        //       4     5   6
        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);

        // 序列化二叉树
        System.out.print("序列化后的二叉树：");
        System.out.println(Serialize(root));

        // 反序列化二叉树
        System.out.print("反序列化后的二叉树：");
        printTree(Deserialize(Serialize(root)));

    }

    /**
     * 仅用于测试时 打印二叉树（中序遍历）
     */

    private static void printTree(TreeNode root) {
        if (root != null) {
            printTree(root.left);
            System.out.print(root.val + " ");
            printTree(root.right);
        }
    }

}

• 测试结果

序列化后的二叉树：1,2,4,#,#,#,3,5,#,#,6,#,#,
反序列化后的二叉树：4 2 1 5 3 6

---

6. Demo地址

Carson_Ho的Github地址：面试37 - 序列化二叉树