エンジニア実践的基礎: バックトラッキング

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

バックトラッキングとは？

バックトラッキングは迷路で出口に通じる道を探るようなアルゴリズムです。誤った方向を選ぶと壁に阻まれて、それ以上進むめません。別の道を探すために元来た道を引き返します。これを繰り返していけば、いずれ出口に到達します。

木でバックトラッキングを使い、リーフノードの値が0のパスが存在するかを確かめましょう。ルートが迷路の入り口で0が出口です。

目視なら赤色のパスをすぐに見つけられます。アルゴリズムでは優先探索で一つひとつノードを探索します。最初に 4 → 3 → 2 と探索します。

0 以外のリーフノードに到達したので、今度は逆に 2 → 3 → 2 と引き返します。

次に 4 → 6 → 5 と探索します。

今回もリーフノードは0ではなかったので引き返します。ただしノード6が右子ノードを持つのでノード4まで引き返さず、ノード7を探索します。

6 → 7 → 0 と探索すると目的のノード0を見つけました。

実装

def leafPath(root, path):
    if not root:
        return False  # ノードが存在しない場合は False を返す

    if not root.left and not root.right and root.val == 0:
        # 値が0のリーフノードに到達した場合は True を返す
        return True
    
    # 左部分木を探索する
    if leafPath(root.left, path):
        return True
    
    # 右部分木を探索する
    if leafPath(root.right, path):
        return True

    # 0 以外の値を持つリーフノードに到達した場合や子ノードがない場合は False を返す
    return False

計算量

最大で全てのノードを探索するため時間計算量は O(n) です。木の高さだけ再帰処理でスタックを積むので、最大の木の高さを h とすると O(h) が空間計算量となります。