题解 | #序列化二叉树#

题目:https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84

ps:只有要遍历多一层空子节点,序列化二叉树的结果就会唯一。比如在前序遍历下表示为:1,2,3,4,#,#,5,#,#,#,#,对应唯一二叉树;但是1,2,3,4,5,不是对应唯一二叉树。

采用前序遍历来序列化二叉树,相比层次遍历有一点好处,虽然说层次遍历遍历起来更直观,但是需要存储更多的空子节点。举例

层次遍历表示下的二叉树:1,2,#,3,#,#,#,4,5,#,#,#,#,#,#,

在前序遍历下表示为:1,2,3,4,#,#,5,#,#,#,#,

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.s=''
        self.index=-1
    def inorder(self, root):#递归函数
        if not root:#递归到没有左右子节点的那种要加"#"表示空子节点
            self.s=self.s + '#,'
            return None
        self.s=self.s+str(root.val)+","
        self.inorder(root.left)
        self.inorder(root.right)            
            
    def Serialize(self, root):#调用递归函数
        if not root:
            self.s='#,'
            return self.s
        self.inorder(root)
        return self.s
                 
    def DeserializeFunction(self, arr):#arr是一个字符数组
        self.index=self.index+1#s[self.index]=='#'时,index要+1;s[self.index]!='#'时,index也要+1              
        if self.index>len(arr) or arr[self.index]=='#':
            return None#如果item是#,不需要构造它的子节点,直接结束。如果self.index>len(s)也直接结束
        node=TreeNode(int(arr[self.index]))
        node.left=self.DeserializeFunction(arr)
        node.right=self.DeserializeFunction(arr)
        return node
        
    def Deserialize(self, s):##调用递归函数        
        if s=='#,':#空树,返回None
            return None
        arr=s.split(",")  
        res=self.DeserializeFunction(arr)
        return res
    
    #关于递归中的return/return None。终止此次内部递归,开始下一轮的递归
全部评论

相关推荐

不亏是提前批,神仙打架,鼠鼠不配了
站队站对牛:现在92都报工艺岗了
投递韶音科技等公司8个岗位
点赞 评论 收藏
分享
不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务