首页技术文章正文

二叉树序列化与反序列化的Java实现

更新时间:2018-12-19 来源:黑马程序员 浏览量:

  二叉树是树的特殊一种,在笔试中较为常见,其具有如下特点:

  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;

  Queuequeue = new LinkedList<>(Arrays.asList(data.split(",")));

  return decode(queue);

  }

  public TreeNode decode(Queuequeue){

  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; }

  }


作者:黑马程序员JavaEE培训学院

首发: http://java.itheima.com

分享到:
在线咨询 我要报名
和我们在线交谈!