//dfs前序遍历
StringBuilder sb=new StringBuilder();
public String serialize(TreeNode root) {
//如果为null,添加N并返回
if(root==null) {
sb.append("N,");
return sb.toString();
}
//不为null时,添加数字,再进入左右子树递归添加
sb.append(root.val+",");
serialize(root.left);
serialize(root.right);
return sb.toString();
}
Deque<String> q;//存储数字
public TreeNode deserialize(String data) {
q=new ArrayDeque<>(Arrays.asList(data.split(",")));//分割数字
return dfs();
}
TreeNode dfs(){
String num=q.poll();
//如果为N说明该节点为null
if(num.equals("N")) return null;
//否则创建新节点,再进入下一层获取左右子树
TreeNode node=new TreeNode(Integer.parseInt(num));
node.left=dfs();
node.right=dfs();
return node;
}
//bfs层序遍历
public static String serialize(TreeNode root) {
StringBuilder sb=new StringBuilder();
List<TreeNode> q=new ArrayList<>();
q.add(root);
while(!q.isEmpty()){
TreeNode n=q.remove(0);
if(n==null)
sb.append("N,");//如果为null,添加N再继续
else{//否则左右子节点入队
sb.append(n.val+",");
q.add(n.left);
q.add(n.right);
}
}
return sb.toString();
}
public static TreeNode deserialize(String data) {
Deque<String> q=new ArrayDeque<>(Arrays.asList(data.split(",")));//分割数字
String s0=q.poll();
if(s0.equals("N")) return null;
Deque<TreeNode> q1=new ArrayDeque<>();//存储节点
TreeNode root=new TreeNode(Integer.parseInt(s0));//创建根节点
q1.add(root);
while(!q.isEmpty()){
TreeNode parent=q1.poll();//q1每次出队的是q出队的两个数的父节点
String s1=q.poll();
if(!s1.equals("N"))
parent.left=new TreeNode(Integer.parseInt(s1));
String s2=q.poll();
if(!s2.equals("N"))
parent.right=new TreeNode(Integer.parseInt(s2));
//子节点为null则不添加
if(parent.left!=null)
q1.add(parent.left);
if(parent.right!=null)
q1.add(parent.right);
}
return root;
}
|
