LeetCode 331. Verify Preorder Serialization of a Binary Tree

この記事はLeetCode331の解答を日本語訳したものです。
元の問題：https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
元の解答：https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution

問題

ある入力に対してBTをpreorderで走査した結果としてありうる場合はtrue,そうでない場合はfalseを返してください。
ここで#はノードがない（null）ことを意味します。
入力例："9,3,4,#,#,1,#,#,2,#,6,#,#"

解答

BTを成り立たせる条件を整理する。nullもノードに含めるとして

• 全てのnullでないノードは２つの子ノード（outdegree）と１つの親ノード（indegree）を持つ
• 全てのnullノードは子ノード（outdegree）が存在せず１つの親ノード（indegree）を持つ

ここで入力の各値に対して

diff = outdegree - indegree

を考える。次の値は正しいノードであれば（rootでない限り）必ず親を１つ持つのでdiff -= 1する。さらにこのノードがnullでない場合は子ノードが２つあるはずなので（nullも子ノードとして考える）diff += 2する。もし入力が正しければdiffは絶対に負の数にはならず、入力の最後まで読んだ時に０になる。

public boolean isValidSerialization(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.equals("#")) diff += 2;
    }
    return diff == 0;
}

さらなる解説

これだけだとBTが成り立たない条件を全て満たしているかわからない。確かにBTではリンクに注目すると親から見た子、子から見た親の差が０になり「diffが負にならない」「diffが最後０になる」を満たさなければBTが成立しないことがわかる。しかしこれはBTが成り立つ条件ではなくBTが成り立たない条件なので、これ以外にBTが成り立たない条件が存在しないこと（ケースに漏れがこと）を証明する必要がある。

（加筆予定）