LeetCoding Challenge Oct. 9: Serialize and Deserialize BST

LeetCode October Challenge の 9 日目。

今日の問題は Serialize and Deserialize BST。

問題の概要

• 与えられた二分探索木を String オブジェクトにシリアライズし、また String オブジェクトから二分探索木 (TreeNode オブジェクト) をデシリアライズするクラス Codec を実装する
  • シリアライズフォーマットは任意のもので OK だが、できる限りコンパクトなフォーマットであるべき

考え方

• とりあえずナイーブなシリアライズ方法を考えてみよう
  • 深さ優先でたどる
    • スタックもしくは再帰で実装できる
  • プリオーダー (行きがけ) に値を取り出す
  • | をデリミタとして、取り出した値を順に並べて文字列化する
    • 存在しないノードは空文字列となるようにする (つまりはデリミタが 2 つ連続する)
• デシリアライズも深さ優先、プリオーダーの処理となる
  • この順にノードを復元していけばいい
  • 文字列から数値を切り出す処理は不要なオブジェクト生成を避けるために String#charAt(int) だけを使うことにする
• このナイーブなアルゴリズムを実装して submit → accept 🤗
  • Runtime 1ms で Your runtime beats 99.73 % of java submissions. 👍
• なお、ノードが保持する値が 0 以上 10000 以下であることを利用し、値を直接 char の値にキャストして文字列化する方法もあるよね
  • この場合は存在しないノードの表現も含めて常に 2 バイト消費するけど、デシリアライズの処理が非常に単純になって高速化が見込める 🤩
  • でも runtime 1ms の壁は破れなかった 😿

おまけ

Runtime 0ms のコード。これはひどい 🤮

コード

public class Codec {
    static final char DELIMITER = '|';

    static class Parser {
        final String data;
        int index;

        Parser(String data) {
            this.data = data;
        }

        int parseNextVal() {
            if (index >= data.length()) {
                return -1;
            }

            int val = 0;
            int begin = index;
            for (char ch; index < data.length() && (ch = data.charAt(index)) != DELIMITER; index++) {
                val = val * 10 + (ch - '0');
            }

            if (begin == index++) {
                return -1;
            }

            return val;
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return serializeRecursive(root, new StringBuilder()).toString();
    }

    StringBuilder serializeRecursive(TreeNode node, StringBuilder builder) {
        if (node == null) {
            return builder.append(DELIMITER);
        }
        builder.append(node.val).append(DELIMITER);
        serializeRecursive(node.left, builder);
        serializeRecursive(node.right, builder);
        return builder;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return deserializeRecursive(new Parser(data));
    }

    TreeNode deserializeRecursive(Parser parser) {
        int val = parser.parseNextVal();
        if (val < 0) {
            return null;
        }

        TreeNode node = new TreeNode(val);
        node.left = deserializeRecursive(parser);
        node.right = deserializeRecursive(parser);
        return node;
    }
}