剑指Offer的学习笔记（C#篇）-- 序列化二叉树

WeiMLing

发布于 2019-08-23 19:47:36

4440

发布于 2019-08-23 19:47:36

文章被收录于专栏：WeiMLing

题目描述

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

一 . 理解题意

二叉树的序列化，是将一个结构化的东西变成扁平化的字符串，序列化二叉树或者是反序列化二叉树就是二叉树和扩展二叉树遍历序列之间的转换。将二叉树中的没个结点的空指针引出一个虚节点，其值为一个特定值，比如说 # 字符，我们成这种处理后的二叉树为原来二叉树的扩展二叉树。扩展二叉树和二叉树是一一对应关系。所以下图的前序的序列化序列为：A B # D # # C # #。

二 . 代码实现与分析

class Solution
    {
        public string Serialize(TreeNode root)
        {
            string result = "";
            //递归结束条件
            if (root == null)
            {
                result += "#,";
                //最终输出
                return result;
            }
            //序列化加数
            result += root.val + ",";
            //递归左子节点
            result += Serialize(root.left);
            //递归右子节点
            result += Serialize(root.right);
            //输出（非最终）
            return result;
        }
        //把它放在外面是有用意的，因为里面为了构造一个连加，这个是为了搞第一个数。
        private int index = -1;
        public TreeNode Deserialize(string str)
        {
            index += 1;
            TreeNode tmp= null;
            //去掉，
            string[] strList = str.Split(',');
            //子节点结束条件
            if (strList[index] != "#")
            {
                //把这个序列化里面的数一个个揪出来
                tmp = new TreeNode(int.Parse(strList[index]));
                //左子节点遍历
                tmp.left = Deserialize(str);
                //右子节点遍历
                tmp.right = Deserialize(str);
            }
            //反序列化输出
            return tmp;
        }
    }