峡江网站建设,wordpress修改标题链接,wordpress文章浏览数,h5网页设计模板297. 二叉树的序列化与反序列化#xff08;困难#xff09;
题目描述#xff1a; 序列化是将一个数据结构或者对象转换为连续的比特位的操作#xff0c;进而可以将转换后的数据存储在一个文件或者内存中#xff0c;同时也可以通过网络传输到另一个计算机环境#xff0c;…297. 二叉树的序列化与反序列化困难
题目描述 序列化是将一个数据结构或者对象转换为连续的比特位的操作进而可以将转换后的数据存储在一个文件或者内存中同时也可以通过网络传输到另一个计算机环境采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式你也可以采用其他的方法解决这个问题。
考察重点通过深度优先遍历DFS对二叉树进行序列化同等的再使用DFS对其序列进行反序列化。
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func Constructor7() Codec {return Codec{str: }
}/**
采用DFS深度优先遍历实现树的序列化为空则置为n
*/
func rSerial(root *TreeNode) string {if root nil {return n}left : , rSerial(root.Left)right : , rSerial(root.Right)sel : strconv.Itoa(root.Val)return sel left right
}// Serializes a tree to a single string.
func (cc *Codec) Serialize(root *TreeNode) string {return rSerial(root)
}/**
通过字符串恢复树同样采用DFS深度优先遍历实现树的反序列化
可以采用两种方式一种是通过返回值给root.Right root.Left赋值一种是通过指针给root.Right root.Left赋值
*/
func rDeserial(tt []string, a int) (int, *TreeNode) {if tt[a] n {return a, nil}v, _ : strconv.Atoi(tt[a])a, LeftT : rDeserial(tt, a1) //深度搜索继续遍历其左右子节点a, RightT : rDeserial(tt, a1)root : TreeNode{v, LeftT, RightT} //给当前结点赋值return a, root
}// Deserializes your encoded data to tree.
func (cc *Codec) Deserialize(data string) *TreeNode {datas : strings.Split(data, ,)if datas[0] n {return nil}_, root : rDeserial(datas, 0)return root
}/**
func rDeserial(datas []string, index int, pre, root *TreeNode) int { //pre负责记录root的父节点在root对应n时将pre.left或者pre.right置为nilword : datas[index]if word ! n {Iword, _ : strconv.Atoi(word)newroot : TreeNode{Val: Iword, Left: TreeNode{}, Right: TreeNode{}} //创建当前结点通过赋值给指针指向位置的方式实现对参数中的root赋值*root newrootindex rDeserial(datas, index1, root, root.Left) //index记录当前遍历的位置index rDeserial(datas, index, root, root.Right)} else {if pre.Left root { //判断root是pre的左子树还是右子树pre.Left nil} else {pre.Right nil}index}return index
}// Deserializes your encoded data to tree.
func (cc *Codec) Deserialize(data string) *TreeNode {root : TreeNode{}datas : strings.Split(data, ,)if datas[0] n {return nil}rDeserial(datas, 0, root, root)return root
}
*/
