二叉树是树的特殊一种，在笔试中较为常见，其具有如下特点：1、每个结点最多有两颗子树，结点的度最大为2。2、左子树和右子树是有顺序的，次序不能颠倒。3、即使某结点只有一个子树，也要区分左右子树。
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Demo {
public String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder encodedStr = new StringBuilder();
encode(root,encodedStr);
return encodedStr.substring(1).toString();
}
public void encode(TreeNode root,StringBuilder sb){
if (root == null){
sb.append(",#");
return;
}
sb.append(",").append(root.val);
encode(root.left,sb);
encode(root.right,sb);
}
public TreeNode deserialize(String data) {
if (data.length() == 0) return null;
Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
return decode(queue);
}
public TreeNode decode(Queue<String> queue){
if (queue.isEmpty()) return null;
String cur = queue.poll();
if (cur.equals("#")) return null;
TreeNode root = new TreeNode(Integer.valueOf(cur));
root.left = decode(queue);
root.right = decode(queue);
return root;
}
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
|
|
收藏
淘帖
踩
