序列化与反序列化二叉树

序列化与反序列化二叉树

题目要求很明确：

使用!来分割值value,使用#来代替null值

根据题意：（采用的是前序遍历，中左右）

1
2 3
4 5 6 7
序列化之后的结果为：1!2!4!#!#!5!#!#!3!6!#!#!7!#!#!

序列化很简单，只需要在遇到null的时候添加#!号，遇到数值添加!即可

    String Serialize(TreeNode root) {
        if (root == null) return "";
        return helpSerialize(root, new StringBuilder()).toString();
    }

    private StringBuilder helpSerialize(TreeNode root, StringBuilder s) {
        if (root == null) return s;
        s.append(root.val).append("!");
        if (root.left != null) {
            helpSerialize(root.left, s);
        } else {
            s.append("#!"); // 为null的话直接添加即可
        }
        if (root.right != null) {
            helpSerialize(root.right, s);
        } else {
            s.append("#!");
        }
        return s;
    }

反序列化的时候，由于采用的是先序遍历，此时如果遇到了#号，我们知道左边结束了,要开启右边，如果再次遇到#,表示当前整个部分的左边结束了要开始右子树。。依次类推。

    private int index = 0; // 设置全局主要是遇到了#号的时候需要直接前进并返回null

    TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0) return null;
        String[] split = str.split("!");
        return helpDeserialize(split);
    }

    private TreeNode helpDeserialize(String[] strings) {
        if (strings[index].equals("#")) {
            index++;// 数据前进
            return null;
        }
        // 当前值作为节点已经被用
        TreeNode root = new TreeNode(Integer.valueOf(strings[index]));
        index++; // index++到达下一个需要反序列化的值
        root.left = helpDeserialize(strings);
        root.right = helpDeserialize(strings);
        return root;
    }

Keep thinking keep coding~