Pythonでジグザグラベル付き二分木のパスを求める方法

ジグザグラベル付き二分木とは

すべてのノードが2つの子を持つ無限の二分木を考えます。この木では、ノードに行順にラベルが付けられており、奇数行(1行目・3行目・5行目…)は左から右へ、偶数行(2行目・4行目・6行目…)は右から左へとラベルが振られます。そのため、木全体は次のようなジグザグ状の構造になります。

このような木において、あるノードのラベルが与えられたとき、ルートからそのノードまでのパス上のラベル一覧を求めるのが本問題です。たとえば入力が label = 14 の場合、出力は [1, 3, 4, 14] となります。

解法のアプローチ

基本的なアイデアは、「ジグザグのラベル順序に従って配列(tree)にノードを順番に格納していき、目的のラベルが見つかったら、インデックスを半分にしながら親ノードをたどる」というものです。配列の先頭にダミーの 0 を入れておくことで、インデックス i の親は常に i // 2 で表せる点がポイントです。

具体的な手順は以下の通りです。

• 配列 tree と res を定義する。tree には最初に 0 と 1 を挿入し、odd := 1、current := 1、two := 2 と初期化する。
• label が 1 の場合は [1] をそのまま返す。
• 目的のラベルが見つかるまで無限ループを回す。
• odd が真のとき(現在の行は左→右方向):
  • max_val := current + two、temp := max_val とする。
  • temp > current の間、temp を tree に挿入する。temp == label なら内側のループを抜け、そうでなければ temp を 1 減らす。
  • tree の末尾が label なら外側のループも抜ける。
  • current := max_val と更新する。
• odd が偽のとき(現在の行は右→左方向):
  • temp := two とする。
  • temp が 0 になるまで、temp を 1 減らし、current を 1 増やして tree に挿入する。current == label になったら抜ける。
  • tree の末尾が label なら外側のループも抜ける。
• 1 行分の処理が終わるごとに two *= 2 とし、odd フラグを反転させる。
• index := len(tree) - 1 とし、index が 0 でない間、tree[index] を res に追加して index := index // 2 と更新することで、葉から根へとさかのぼる。
• 最後に res を反転して返せば、ルートから対象ノードまでのパスが得られる。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution(object):
    def pathInZigZagTree(self, label):
        tree = []
        res = []
        tree.append(0)
        tree.append(1)
        odd = 1
        current = 1
        two = 2
        if label == 1:
            return [1]
        while True:
            if odd:
                max_val = current + two
                temp = max_val
                while temp > current:
                    tree.append(temp)
                    if temp == label:
                        break
                    temp -= 1
                if tree[-1] == label:
                    break
                current = max_val
            else:
                temp = two
                while temp:
                    temp -= 1
                    current += 1
                    tree.append(current)
                if current == label:
                    break
                if tree[-1] == label:
                    break
            two *= 2
            odd = not odd
        index = len(tree) - 1
        while index:
            res.append(tree[index])
            index //= 2
        res = res[::-1]
        return res
ob = Solution()
print(ob.pathInZigZagTree(14))

入力

14

出力

[1,3,4,14]

まとめ

各レベルのノード数は 2, 4, 8, … と倍々に増えていくため、このアルゴリズムの計算量はラベルのビット長に対して線形、すなわち O(log n) で収まります。ジグザグの並び順を配列に忠実に再現しておけば、あとは単純なインデックス操作だけで親子関係をたどれるのがこの解法の美しいところです。