[Google] Serialization and Deserialization BST 二叉树编码和解码

这是一道Google的面试题. 当我第一次看到这题的时候, 第一个感觉, 树, 编码,解码, 那不就是Prufer Code么. 拿起笔就开始写, 后来感觉电面不应该这么复杂, 而且Prufer code对象是Labeled Tree, 这里并没有使用到BST的特殊性质. 于是赶紧回想刷过的题, 突然想起Leetcode上面的编码方式:

这个编码的特点是:

1. Inorder Traversal.
2. Null = #
3. Code容易写.

所以编码的code是:

public static String serialize (TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null)
            sb.append("#");
        else {
            sb.append(root.val);
            sb.append(serialize(root.left));
            sb.append(serialize(root.right));
        }
        return sb.toString();
    }

解码的特点是:

1. 因为已知编码是Inorder, 所以解码也是Inorder
2. 要注意如果解码到#, 需要return null.

所以解码的code是:

static int index = 0;
    public static TreeNode deserialize (String s) {
        if (index >= s.length()) {
            return null;
        }
        else {
            char c = s.charAt(index);
            if (c == '#'){
                index++;
                return null;
            }else {
                TreeNode root = new TreeNode(s.charAt(index) - 48);
                index++;
                root.left = deserialize(s);
                root.right = deserialize(s);
                return root;
            }
        }
    }