449. Serialize and Deserialize BST

参考 297. Serialize and Deserialize Binary Tree

Version #4 LC DFS Iteration

二刷
Version # 1 DFS Recursion using the property of binary search tree

Since we can guarantee that the root node value is larger than nodes in its left subtree and less than nodes in its right substree, we can deserialize a tree from its pre-order traversal
89.68 %
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        seHelper(root, sb);
        return sb.toString();
    }
    private void seHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        sb.append(node.val);
        sb.append(",");
        seHelper(node.left, sb);
        seHelper(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] strs = data.split(",");
        return deHelper(strs, 0, strs.length);
    }
   
    // [start, end)
    private TreeNode deHelper(String[] strs, int start, int end) {
        if (start >= end) {
            return null;
        }
        int val = Integer.valueOf(strs[start]);
        TreeNode node = new TreeNode(val);
        int mid = start + 1;
        // left -> [start + 1, mid) right -> [mid, end)
        while (mid < end && Integer.valueOf(strs[mid]) < val) {
            mid++;
        }
        node.left = deHelper(strs, start + 1, mid);
        node.right = deHelper(strs, mid, end);
        return node;
    }
}


一刷
Version #3 LC DFS Recursion
自己写了一个Tuple Class 用了Recursion
是一个general binary tree的写法 没有利用BST的性质

80.02 %
class Tuple {
    int index;
    TreeNode node;
    public Tuple(int index, TreeNode node) {
        this.index = index;
        this.node = node;
    }
}
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
   
        StringBuilder sb = new StringBuilder();
        traversal(root, sb);
        sb.deleteCharAt(sb.length() - 1);
        //System.out.println(sb.toString());
        return sb.toString();
    }
    // pre-order traversal
    private void traversal(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("#,");
            return;
        }
        sb.append(root.val + ",");
        traversal(root.left, sb);
        traversal(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) return null;
        String[] nodes = data.trim().split(",");
        return build(nodes,  0).node;
    }
    private Tuple build(String[] nodes, int index) {
        if (nodes[index].equals("#")) return new Tuple(index, null);
   
        TreeNode root = new TreeNode(Integer.valueOf(nodes[index]));
        Tuple left = build(nodes, index + 1);
        Tuple right = build(nodes, left.index + 1);
        root.left = left.node;
        root.right = right.node;
        return new Tuple(right.index, root);
    }
}