剑指Offer-序列化反序列化二叉树

た 入场券 2022-05-22 04:42 307阅读 0赞

转自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
;


    
}


}
;

发表评论

表情:
评论列表 (有 0 条评论,307人围观)

还没有评论,来说两句吧...

相关阅读

    相关 offer序列

    试题: 请实现两个函数,分别用来序列化和反序列化二叉树 代码: 二叉树有三种遍历方式前序,中序,后序;而在其中中序遍历完以后根节点是第一个便利的,有利于我们重新构建