AcWing 50. 序列化二叉树 java宽搜版
原题链接
困难
作者:
哂大猫
,
2021-05-29 13:07:16
,
所有人可见
,
阅读 214
样例
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Queue<TreeNode> res= new LinkedList<TreeNode>();
String s="";
// Encodes a tree to a single string.
String serialize(TreeNode root) {
if(root==null) return s="null";
res.add(root);
while(res.isEmpty()==false){
TreeNode cur=res.poll();
if(cur!=null){
s=s+cur.val+",";
if(cur.left==null&&cur.right!=null) res.add(null);
if(cur.left!=null) res.add(cur.left);
if(cur.right!=null) res.add(cur.right);
if(cur.right==null&&cur.left!=null) res.add(null);
if(cur!=null&&cur.right==null&&cur.left==null) {
res.add(null);
res.add(null);
}
}
else{
s=s+"null"+",";
}
}
//System.out.println(s);
return s;
}
// Decodes your encoded data to tree.
TreeNode deserialize(String data) {
if(data.equals("")) return null;
String[] n=data.split(",");
//初始化节点
TreeNode t[]=new TreeNode[n.length];
for(int i=0;i<n.length;i++){
if(n[i].equals("null")) t[i]=null;
else t[i]=new TreeNode(Integer.parseInt(n[i]));
}
//处理头节点
if(n[0].equals("null")) return null;
else{
t[0].left=t[1];
t[0].right=t[2];
}
//处理左子树和右子树
int cn=1;
int cellT=1;
while(cn<n.length){
int temp=cellT;
cellT=0;
int tempcn=cn;
for(int i=0;i<2*temp;i++){
if(n[cn].equals("null")==false){
cellT++;
//System.out.println(tempcn+(int)Math.pow(2,temp)+(cellT-1)*2);
t[cn].left=t[tempcn+2*temp+(cellT-1)*2];
t[cn].right=t[tempcn+2*temp+(cellT-1)*2+1];
}
cn++;
}
}
return t[0];
}
}