Day 17

zhanglei 2022年08月07日 833次浏览

Day 17

剑指offer 37.序列化二叉树

题目描述

image-20220807195349288

image-20220807195349288

思路

利用队列可以实现层序遍历

解答

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. public class Codec {
  11. public String serialize(TreeNode root) {
  12. if(root == null) return "[]";
  13. StringBuilder res = new StringBuilder("[");
  14. Queue<TreeNode> queue = new LinkedList<>();
  15. queue.add(root);
  16. while(!queue.isEmpty()) {
  17. TreeNode node = queue.poll();
  18. if(node != null) {
  19. res.append(node.val + ",");
  20. queue.add(node.left);
  21. queue.add(node.right);
  22. }
  23. else res.append("null,");
  24. }
  25. res.deleteCharAt(res.length() - 1);
  26. res.append("]");
  27. return res.toString();
  28. }

  29. public TreeNode deserialize(String data) {
  30. if(data.equals("[]")) return null;
  31. String[] vals = data.substring(1, data.length() - 1).split(",");
  32. TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
  33. Queue<TreeNode> queue = new LinkedList<>();
  34. queue.add(root);
  35. int i = 1;
  36. while(!queue.isEmpty()) {
  37. TreeNode node = queue.poll();
  38. if(!vals[i].equals("null")) {
  39. node.left = new TreeNode(Integer.parseInt(vals[i]));
  40. queue.add(node.left);
  41. }
  42. i++;
  43. if(!vals[i].equals("null")) {
  44. node.right = new TreeNode(Integer.parseInt(vals[i]));
  45. queue.add(node.right);
  46. }
  47. i++;
  48. }
  49. return root;
  50. }
  51. }



  52. // Your Codec object will be instantiated and called as such:
  53. // Codec codec = new Codec();
  54. // codec.deserialize(codec.serialize(root));