/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root==null)return "[]";
StringBuilder res = new StringBuilder("[");
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node!=null){
res.append(node.val+",");
queue.add(node.left);
queue.add(node.right);
}
else res.append("null,");
}
//删除最后一个，
res.deleteCharAt(res.length() -1 );
res.append("[");
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
String[] val = data.substring(1,data.length()-1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(val[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int i = 1 ;
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(!val[i].equals("null")){//不为空
node.left = new TreeNode(Integer.parseInt(val[i]));
queue.add(node.left);
}
i++;
if(!val[i].equals("null")){
node.right = new TreeNode(Integer.parseInt(val[i]));
queue.add(node.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "[]";
// 建立队列
Queue<TreeNode> queue = new LinkedList<>(){{offer(root);}};
StringBuilder res = new StringBuilder("[");
// 开始遍历
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
res.append(node.val + ",");
queue.offer(node.left);
queue.offer(node.right);
} else {
res.append("null,");
}
}
res.deleteCharAt(res.length()-1);
res.append("]");
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("[]")) return null;
// 对字符串进行分离
String[] vals = data.substring(1, data.length()-1).split(",");
// 建立根节点
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
// 建立队列
Queue<TreeNode> queue = new LinkedList<>(){{offer(root);}};
// 定义索引
int i = 1;
// 遍历队列
while (i < vals.length) {
TreeNode node = queue.poll();
if (!vals[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(vals[i]));
queue.offer(node.left);
}
i++;
if (!vals[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(vals[i]));
queue.offer(node.right);
}
i++;
}
return root;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
if(root == null) return '';
let res = '';
let q = [root]
while(q.length != 0) {
let cur = q.shift()
// 左节点入队
if(cur != null) {
q.push(cur.left)
q.push(cur.right)
res += cur.val + ','
} else {
res += 'null,'
}
}
return res
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
if(data.length <= 0 || data == null) return null
let res = data.split(',')
let head = new TreeNode(parseInt(res[0]))
let q = [head]
let i = 1
while(q.length != 0) {
let cur = q.shift()
// 构建左节点
if(res[i] != 'null') {
let left = new TreeNode(parseInt(res[i]))
cur.left = left
q.push(left)
}
i++
// 构建右节点
if(res[i] != 'null') {
let right = new TreeNode(parseInt(res[i]))
cur.right = right
q.push(right)
}
i++
}
return head
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree into a single string.
public String serialize(TreeNode root) {
return solveSerialize(root,"");
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] dataArray=data.split(",");
List<String> dataList=new LinkedList<String> (Arrays.asList(dataArray));
return solveDeserialize(dataList);
}
public String solveSerialize(TreeNode root,String str){
if(root==null)
str+="null,";
else {
str+=String.valueOf(root.val) + ",";
str=solveSerialize(root.left,str);
str=solveSerialize(root.right,str);
}
return str;
}
public TreeNode solveDeserialize(List<String> data){
if(data.get(0).equals("null")) {
data.remove(0);
return null;
}
TreeNode root=new TreeNode(Integer.valueOf(data.get(0)));
data.remove(0);
root.left=solveDeserialize(data);
root.right=solveDeserialize(data);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
s(root, sb);
return sb.toString();
}
public void s(TreeNode root, StringBuilder sb){
if(root == null){
sb.append("#,");
}else{
sb.append(root.val).append(",");
s(root.left, sb);
s(root.right, sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
cnt = 0;
String[] vals = data.split(",");
return d(vals);
}
public static int cnt;
public TreeNode d(String[] vals){
String cur = vals[cnt++];
if(cur.equals("#")){
return null;
}else{
TreeNode head = new TreeNode(Integer.parseInt(cur));
head.left = d(vals);
head.right = d(vals);
return head;
}
}
}
/**
解题思路：按先序遍历顺序序列化/反序列化二叉树即可，空节点用null表示
*/
public class Codec {
String[] preOrder;
Integer idx;
static final String nullVal = "null";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null){
return nullVal;
}
String val = root.val + "";
return val + "," + serialize(root.left) + ',' + serialize(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
this.preOrder = data.split(",");
this.idx = 0;
return deserialize();
}
public TreeNode deserialize() {
String val = preOrder[idx];
idx++;
if (nullVal.equals(val)){
return null;
}
int value = Integer.parseInt(val);
TreeNode node = new TreeNode(value);
node.left = deserialize();
node.right = deserialize();
return node;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
StringBuilder s = new StringBuilder("[");
if (root == null)
return "[]";
q.add(root);
TreeNode node = new TreeNode();
while (q.size() != 0) {
node = q.poll();
if (node != null) {
s.append(node.val + ",");
q.add(node.left);
q.add(node.right);
} else {
s.append("null,");
}
}
s.deleteCharAt(s.length() - 1);
s.append("]");
return s.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("[]"))return null;
String[] split = data.substring(1,data.length()-1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(split[0]));
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
int i = 1;
while(!q.isEmpty()){
TreeNode node = q.poll();
if(!split[i].equals("null")){
node.left = new TreeNode(Integer.parseInt(split[i]));
q.add(node.left);
}
i++;
if(!split[i].equals("null")){
node.right = new TreeNode(Integer.parseInt(split[i]));
q.add(node.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
public class Codec {
List<TreeNode> list = new ArrayList<>();;
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
// 前序遍历 记录
preOrder(root);
String ans = "";
for(TreeNode current: list){
if(current == null){
ans += "null";
}else{
ans += current.val;
}
ans += " ";
}
return ans;
}
public void preOrder(TreeNode node){
if(node == null){
list.add(null);
return;
}
list.add(node);
preOrder(node.left);
preOrder(node.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] spilt = data.split(" ");
return preOrderBuild(spilt);
}
int index = 0;
public TreeNode preOrderBuild(String[] nodeNum){
if(nodeNum.length == index){
return null;
}
if(nodeNum[index].equals("null")){
return null;
}else{
TreeNode current = new TreeNode(Integer.parseInt(nodeNum[index]));
index ++;
current.left = preOrderBuild(nodeNum);
index ++;
current.right = preOrderBuild(nodeNum);
return current;
}
}
}
shuaidi
共以下 14 个回答
LCR 156. 序列化与反序列化二叉树
层序遍历，存储一个完全二叉树，这时可以仅凭一个序列反向还原二叉树
解题思路
– 层序遍历是可以原样进行还原的，需要把null节点也存储下来，这样才能知道左右节点谁为null
– 在序列化时，队列（要放节点）的作用是控制访问顺序（相当于一个跳跃的指针，不是链表或者数组里面指针可以实现的），这个跳跃指针可以按照层序的方式进行访问
– 在反序列化的时候，队列（要放节点）的作用也是跳跃指针可以按照层序的方式进行访问。那如何找到当前节点的左右节点的值呢？通过数组的指针从左到右去完成。相当于队列负责二叉树的顺序控制，数组的下标负责数组的顺序控制。
【题解1】
时间复杂度O(n)，空间复杂度O(n)
思路：跟着视频来看的思路，自己看题的时候这种有点不知道要怎么处理，没理解题目意思。
层序遍历完成序列化和反序列化
先序遍历然后重建二叉树
on on
用字符串记录层序遍历结果，null节点也记录，再反向重建二叉树。
时间复杂度O(N)，空间复杂度O(N)。
利用前序遍历序列化和反序列化
思路：使用同样的方式遍历二叉树，将其转换为字符串，或是将其转换为二叉树。
时间复杂度：O(n)
空间复杂度：O(n)
层序遍历
时间复杂度O(n)
空间复杂度O(n)
//前序递归遍历
public class Codec {
}
思路： 使用 前序遍历 转为String 在使用前序遍历的方式创建二叉树