力扣 449 序列化和反序列化二叉搜索树

题意：给定一个BST，serialize和deserialize它和string

思路：

1. 先序遍历serialize tree成string
2. 用queue，把string放入queue中，并根据当前值与max和min的关系，来重构BST，具体见代码

思想：树的先序遍历

复杂度：时间O（n)，空间O(n)

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
      if (root == null) {
        return "";
      }
      
      StringBuilder sb = new StringBuilder();
      preorderDfs(root, sb);
      return sb.toString();
    }
    
    private void preorderDfs(TreeNode root, StringBuilder sb) {
      sb.append(root.val).append(',');
      if (root.left != null) {
        preorderDfs(root.left, sb);
      }
      if (root.right != null) {
        preorderDfs(root.right, sb);
      }
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
      if (data == null || data.isEmpty()) {
        return null;
      }
      Queue<Integer> values = new LinkedList<>();
      for (String value : data.split(",")) {
        values.add(Integer.valueOf(value));
      }
      return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, values);
    }
    
    private TreeNode helper(int min, int max, Queue<Integer> values) {
      if (values.isEmpty()) {
        return null;
      }
      int value = values.peek();
      if (value <= min || value >= max) {
        return null;
      }
      values.poll();
      TreeNode root = new TreeNode(value);
      root.left = helper(min, value, values);
      root.right = helper(value, max, values);
      return root;
    }
}