当前位置:  首页>> 技术小册>> 数据结构与算法(下)

题目描述

请实现两个函数,分别用来序列化和反序列化二叉树。使用前序遍历实现,空节点使用字符# 表示。

比如有如下二叉树:

  1. 1
  2. 2 3
  3. 4 # 5 6
  4. # # # # # #

序列化的结果为 1,2,4,#,#,#,3,5,#,#,6,#,#

反序列化的结果为上述二叉树

解法

使用前序遍历进行序列化和反序列化。对格式没有要求,只要序列化得到的结果,再反序列化后能与原树相同即可。

  1. /**
  2. * @author mcrwayfun
  3. * @version 1.0
  4. * @description
  5. * @date Created in 2019/1/12
  6. */
  7. public class Solution {
  8. public String Serialize(TreeNode root) {
  9. StringBuilder res = new StringBuilder();
  10. if (root == null) {
  11. return res.toString();
  12. }
  13. serializeHelper(root, res);
  14. // 移除最后一个的符号","
  15. res.deleteCharAt(res.lastIndexOf(","));
  16. return res.toString();
  17. }
  18. private void serializeHelper(TreeNode root, StringBuilder res) {
  19. if (root == null) {
  20. res.append("#");
  21. res.append(",");
  22. return;
  23. }
  24. res.append(root.val);
  25. res.append(",");
  26. serializeHelper(root.left, res);
  27. serializeHelper(root.right, res);
  28. }
  29. private int index = -1;
  30. public TreeNode Deserialize(String str) {
  31. if (str == null || str.length() == 0) {
  32. return null;
  33. }
  34. String[] treeNodeStr = str.split(",");
  35. return deserializeHelper(treeNodeStr);
  36. }
  37. private TreeNode deserializeHelper(String[] treeNodeStr) {
  38. index++;
  39. TreeNode node = null;
  40. // index不越界并且当前节点不为#
  41. if (index < treeNodeStr.length && !"#".equals(treeNodeStr[index])) {
  42. node = new TreeNode(Integer.valueOf(treeNodeStr[index]));
  43. node.left = deserializeHelper(treeNodeStr);
  44. node.right = deserializeHelper(treeNodeStr);
  45. }
  46. return node;
  47. }
  48. }

测试用例

  1. 功能测试(输入的二叉树是完全二叉树;所有节点都没有左/右子树的二叉树;只有一个节点的二叉树;所有节点的值都相同的二叉树);
  2. 特殊输入测试(指向二叉树根结点的指针为空指针)。

该分类下的相关小册推荐: