Day 17
剑指offer 37.序列化二叉树
题目描述
思路
利用队列
可以实现层序遍历
。
解答
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
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();
}
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<>();
queue.add(root);
int i = 1;
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
if(!vals[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.left);
}
i++;
if(!vals[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(vals[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));