Pythonで二分木の葉から始まる辞書順最小の文字列を求める方法

問題概要

二分木のルートノードが与えられます。各ノードには0から25までの値が格納されており、これらは文字「a」から「z」に対応しています。つまり、0は「a」、1は「b」というように対応付けられています。

このとき、木の葉から始まってルートで終わるパスの中で、辞書順（lexicographical order）で最も小さい文字列を見つける必要があります。

例えば、次のような木を考えてみましょう。

この場合、パスの値の並びは [0, 3, 25] となるため、出力は "adz" になります。

解法のアプローチ

この問題はDFS（深さ優先探索）を使って解くことができます。以下の手順で進めます。

• DFS走査用のメソッドを定義する

• ノードがnullでない場合：

  • ノードの値を対応する文字に変換し、配列Aに追加する

  • ノードが左右どちらも子を持たない（葉である）場合：

    • ans を、ans と「Aの要素を逆順に連結した文字列」のうち小さい方で更新する

    • Aから末尾の要素を削除する

    • 処理を終了して戻る

  • 左の子に対して dfs(node.left, A) を実行する

  • 右の子に対して dfs(node.right, A) を実行する

  • Aから末尾の要素を削除する

  • 戻る

• 本体のメソッドは以下のように構成する：

• ans の初期値を "~" とする（ASCIIコード上、小文字より大きい値のため初期値として適切）

• dfs(root, 空の配列A) を呼び出す

• ans を返す

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right
def insert(temp,data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)
def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree
class Solution(object):
    def smallestFromLeaf(self, root):
        self.ans = "~"
        self.dfs(root,[])
        return self.ans
    def dfs(self, node, A):
        if node:
            A.append(chr(node.data + ord('a')))
            if not node.left and not node.right:
                self.ans = min(self.ans, ''.join(reversed(A)))
                A.pop()
                return
        self.dfs(node.left,A)
        self.dfs(node.right,A)
        A.pop()
        return
root = make_tree([25,1,3,1,3,0,2])
ob = Solution()
print(ob.smallestFromLeaf(root))

入力

[25,1,3,1,3,0,2]

出力

adz

解説のポイント

このアルゴリズムのポイントは以下の通りです。

• バックトラッキング：再帰的に子ノードへ降りていく際、配列Aに文字を追加し、処理が終わったら必ず削除（pop）することで、現在のパスだけを正確に追跡できます。

• 逆順での比較：文字列は「葉からルートへ」向かって構成されるため、Aに蓄積された文字を reversed() で逆順にしてから比較します。

• 初期値 "~" の工夫：ASCIIコードでは小文字アルファベット（97〜122）よりも "~"（126）の方が大きいため、どんな結果とも正しく比較できます。

計算量は、各ノードを一度ずつ訪問するため O(N)、ただし葉ごとに文字列の生成と比較が発生するため、最悪の場合は O(N²) となります。