题解 | JAVA 先序 Scanner #序列化二叉树# [P1]

整体思路 - serialize和deserialize都用先序遍历实现

题目里的例子：

先序遍历就用标准recursion，null用#表示，node用“|"分割：

  visit(root);
  recurse(left);
  recurse(right);

serialize结果："1|2|#|#|3|6|#|#|7|#|#|" (最后多个"|"，但是不影响)

deserialize可以直接把Scanner当queue用。Scanner.next()相当于Queue.poll().
在每个node Scanner所看到的String对应的是

node1: "1|2|#|#|3|6|#|#|7|#|#|"
node2: "2|#|#|3|6|#|#|7|#|#|"
node3: "3|6|#|#|7|#|#|"
node6: "6|#|#|7|#|#|"
以此类推

最后别忘了用try block去autoclose scanner。

具体代码：

import java.util.*;

public class Solution {
    String Serialize(TreeNode root) {
      if (root == null) return "";
      preOrderSerialize(root, new StringBuilder());
      return sb.toString();
    }
    
    void preOrderSerialize(TreeNode root, StringBuilder sb) {
      if (root == null) {
        sb.append("#|");
        return;
      } else {
        sb.append(String.valueOf(root.val)).append("|");
      }
      preOrderSerialize(root.left, sb);
      preOrderSerialize(root.right, sb);
    }
  
    TreeNode Deserialize(String str) {
      if (str.isEmpty()) return null;
      try (Scanner sc = new Scanner(str).useDelimiter("\\|")) {
        return preOrderDeserialize(sc);
      }
    }
  
    // Returns the tree deserialzed starting from the next() token.
    TreeNode preOrderDeserialize(Scanner sc) {
      String token = sc.next();
      if (token.equals("#")) { 
        return null; 
      }
      TreeNode n = new TreeNode(Integer.parseInt(token));
      n.left = preOrderDeserialize(sc);
      n.right = preOrderDeserialize(sc);
      return n;
    }
}