哪些网站可以免费看剧,河北网络营销推广seo,衡水建设投资集团网站,soho在哪里做网站文章目录 题目描述简化题目思路分析 题目描述 请实现两个函数#xff0c;分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑#xff0c;你只需要保证一个二叉树可以被序列化为一个字符串并且将… 文章目录 题目描述简化题目思路分析 题目描述 请实现两个函数分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 简化题目
这题实际上就是给了两个函数A和B。 A的功能给树的root输出str类型的层次遍历结果。 B的功能给str类型的层次遍历结果构造树。
不过这里的层次遍历需要加上null。 比如下面这张图输出结果就是[1,2,3,null,null,4,5]
思路分析
通常使用的前序、中序、后序、层序遍历记录的二叉树的信息不完整即唯一的输出序列可能对应着多种二叉树可能性。题目要求的 序列化 和 反序列化 是 可逆操作 。因此序列化的字符串应携带 完整的二叉树信息 。
也就是要加上叶子结点的null在对应的位置。
一、A函数给树root输出字符串。 这个比较容易就是层次遍历就行了遇到空节点记得加入null。 最后在return的时候要注意人家要的是字符串型列表。
ef serialize(self, root):if not root:return []queue []res []queue.append(root)while queue:node queue.pop()if node:res.append(str(node.val))queue.insert(0,node.left)queue.insert(0,node.right)else:res.append(null)return [ ,.join(res) ]
二、B函数给字符串构造树
该函数给的是字符串。所以要先提取出来列表方便后面使用。
vals data[1:-1].split(,)假设题目所给字符串下图所示 设置一个 i 变量来遍历vals。
与传统构造树的方法基本一样。
当vals[i] 为非null的时候构造树。 为null的时候i往后挪不做其余操作。
可以这样理解对于叶子节点其左右都是null。每次构造一个节点就判断下一个 vals[i] 的值是否为null若为null就不构造子树i 继续往后挪。 当左右子树都判断完了就继续下一轮循环重新从队列中取出新的节点。
看下面这张图帮助理解 此时 i 指向第一个null既在循环中判断vals[I] 为null则不构建节点2的左子树i往后挪继续判断又是null就不构建 节点2 的右子树 i 继续往后。 后面又进行新一轮的while从队列中取出新的节点3再次判断vals[i]。。。。以此列推 def deserialize(self, data):if data []:return i 1queue []vals data[1:-1].split(,) # 提取列表root TreeNode(val vals[0]) # 构造根节点queue.append(root)while queue:node queue.pop()if vals[i] ! null:node.left TreeNode(val int(vals[i]))queue.insert(0,node.left)i1if vals[i] !null:node.right TreeNode(valint(vals[i]))queue.insert(0,node.right)i1return root
