剑指Offer-序列化反序列化二叉树
转自http://cuijiahua.com/blog/2018/01/basis_61.html
一、前言
本系列文章为《剑指Offer》刷题笔记。
刷题平台:牛客网
书籍下载:共享资源
二、题目
请实现两个函数,分别用来序列化和反序列化二叉树。
1、思路
这道题思路简单,使用前序遍历来序列化和发序列化即可。只要自己写的程序格式对应上即可。可以使用$符号表示NULL,同时每个结点之间,需要添加逗号,即’,’进行分隔。
直接看代码即可。
2、代码
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | / struct TreeNode { int val; struct TreeNode left; struct TreeNode right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; / class Solution { public : char Serialize ( TreeNode root ) { if ( ! root ) { return NULL ; } string str ; SerializeCore ( root , str ) ; // 把str流中转换为字符串返回 int length = str . length ( ) ; char res = new char [ length + 1 ] ; // 把str流中转换为字符串返回 for ( int i = 0 ; i < length ; i ++ ) { res [ i ] = str [ i ] ; } res [ length ] = ‘\0’ ; return res ; } TreeNode Deserialize ( char str ) { if ( ! str ) { return NULL ; } TreeNode res = DeserializeCore ( &str ) ; return res ; } void SerializeCore ( TreeNode root , string & str ) { // 如果指针为空,表示左子节点或右子节点为空,则在序列中用#表示 if ( ! root ) { str += ‘#’ ; return ; } string tmp = to_string ( root -> val ) ; str += tmp ; // 加逗号,用于区分每个结点 str += ‘,’ ; SerializeCore ( root -> left , str ) ; SerializeCore ( root -> right , str ) ; } // 递归时改变了str值使其指向后面的序列,因此要声明为char** TreeNode DeserializeCore ( char str ) { // 到达叶节点时,调用两次,都返回null,所以构建完毕,返回父节点的构建 if ( str == ‘#’ ) { ( str ) ++ ; return NULL ; } // 因为整数是用字符串表示,一个字符表示一位,先进行转换 int num = 0 ; while ( str != ‘,’ && str != ‘\0’ ) { num = num 10 + ( ( str ) - ‘0’ ) ; ( str ) ++ ; } TreeNode root = new TreeNode ( num ) ; if ( str == ‘\0’ ) { return root ; } else { ( * str ) ++ ; } root -> left = DeserializeCore ( str ) ; root -> right = DeserializeCore ( str ) ; return root ; } } ; |
还没有评论,来说两句吧...