Pythonで木構造の葉の最小の深さを求める方法

Question

前提・実現したいこと

プログラミング初心者です.
木構造の葉の最小の深さを再帰プログラミングを用いて求めようとしています。
例えば、以下の木構造では最小の深さはB:8の1となります。

A: 2
  │
  ├──B: 8
  │
  └──C: 5
     │
     ├──D: 11
     │  │
     │  └──F: 5
     │
     └──E: 6

発生している問題・エラーメッセージ

ところが、現状のコードでは最小の深さが5である以下の木構造でも出力が1となってしまいます。
自力では長時間考えても糸口が掴めませんでした。どなたか解決策を教えていただけますでしょうか。

A: 1
  │
  └──A: 2
     │
     └──E: 3
        │
        └──A: 4
           │
           └──I: 5
              │
              └──A: 6

現状のソースコード

def min_depth_func(tree):   #treeは木構造のインスタンス、引数はtreeのみ
    if tree.num_children() == 0:
        print("base route")
        return 1

    num_depth = 0
    depth_lst = []
    for kid in tree.children:
        num_depth += min_depth_func(kid)
        depth_lst.append(num_depth)
        min_depth = min(depth_lst)
    return min_depth

Answer 1

考え方の参考として、コード例を挙げておきます。考え方を示すことが目的なので、この回答ではツリーが以下のようなJSONで与えられ、これをパースして得られるdictを処理対象のツリーとします。

{
   "id":1,
   "children":[
      {
         "id":8
      },
      {
         "id":5,
         "children":[
            {
               "id":11,
               "children":[
                  {
                     "id":55
                  }
               ]
            },
            {
               "id":6
            }
         ]
      }
   ]
}

上記のJSONをパースして出来るdicttree を引数として与え、最も浅いところの葉のdepthと、そのdepthの深さにある（複数存在する可能性のある）葉の中で最初にみつけたもののidを持つdict
(たとえば、 {'id': 8, 'depth': 1} )
を返す関数として、min_depth_func(tree)を作成しました。

def min_depth_func(tree):
    min_depth_node = {'id': -1, 'depth': None}

    def update_min_depth_node_recursively(node, depth=0):
        nonlocal min_depth_node

        min_depth = min_depth_node['depth']
        if 'children' not in node:
            if min_depth is None or depth < min_depth:
                min_depth_node = {'id': node['id'], 'depth': depth}
        else:
            if min_depth is None or depth + 1 <= min_depth:
                for child in node['children']:
                    update_min_depth_node_recursively(child, depth + 1)

    update_min_depth_node_recursively(tree)

    return min_depth_node

子ノードを左から調べていき、min_depth_nodeを更新します。最も浅い葉を特定するのが目的なので、min_depth_node['depth'] より深い位置へは降りていかないようにしています。

以下は、５個のテストツリーで、上記のmin_depth_func(tree) を試すコードです。

if __name__ == '__main__':
    import json

    # test_1: min_width=1 (id: 8)
    test_1 = '''{
       "id":1,
       "children":[
          {
             "id":8
          },
          {
             "id":5,
             "children":[
                {
                   "id":11,
                   "children":[
                      {
                         "id":55
                      }
                   ]
                },
                {
                   "id":6
                }
             ]
          }
       ]
   }'''

    # test_2: min_width=1 (id: 8)
    test_2 = '''{
        "id":1,
        "children":[
           {
              "id":5,
              "children":[
                 {
                    "id":11,
                    "children":[
                       {
                          "id":55
                       }
                    ]
                 },
                 {
                    "id":6
                 }
              ]
           },
           {
              "id":8
           }
        ]
    }'''

    # test_3: min_width=0 (id: 1)
    test_3 = '''{
       "id":1
    }'''

    # test_4: min_width=2 (id: 5)
    test_4 = '''{
       "id":1,
       "children": [
          { "id": 2, "children": [ { "id": 5 } ]  },
          { "id": 3, "children": [ { "id": 6 } ]  },
          { "id": 4, "children": [ { "id": 7 } ]  }
       ]
    }'''

    # test_5: min_width=1 (id: 8)
    test_5 = '''{
       "id":1,
       "children": [
          { "id": 2, "children": [ { "id": 5 } ]  },
          { "id": 3, "children": [ { "id": 6 } ]  },
          { "id": 4, "children": [ { "id": 7 } ]  },
          { "id": 8 }
       ]
    }'''

    for i, test_json in enumerate([test_1, test_2, test_3, test_4, test_5]):
        tree_root = json.loads(test_json)
        result = min_depth_func(tree_root)
        print(f'test_{i+1}: min_depth_node={result}')

出力結果：

test_1: min_depth_node={'id': 8, 'depth': 1}

test_2: min_depth_node={'id': 8, 'depth': 1}
test_3: min_depth_node={'id': 1, 'depth': 0}
test_4: min_depth_node={'id': 5, 'depth': 2}
test_5: min_depth_node={'id': 8, 'depth': 1}

**動作確認用サンプル: ** ???? tera: [e-mail]/@kilesa

備考： ツリーのノードがどのようなデータ構造であるせよ、再帰による探索中に、不必要に深いところまで調べないで済むようなロジックを入れられるといいですね。

Comments

[aya0425]

ご回答いただきありがとうございます。
詳細にご説明いただいたお陰で今回の概念の理解がとても深まりました。
ひとまず、実装したいこともあり、今回のベストアンサーには元のコードを活用した他の方を選ばせていただきましたが大変助かりました！

Answer 2

以下のような感じでどうでしょうか?

class Tree:
    def __init__(self, val):
        self.val = val
        self.children = []

    def num_children(self):
        return len(self.children)


def min_depth_func(tree):
    if tree.num_children() == 0:
        return 1

    depth_lst = []
    for kid in tree.children:
        depth_lst.append(min_depth_func(kid))
    return 1 + min(depth_lst)


A = Tree(1)
B = Tree(8)
C = Tree(5)
D = Tree(11)
E = Tree(6)
F = Tree(5)
A.children.append(B)
A.children.append(C)
C.children.append(D)
C.children.append(E)
D.children.append(F)
ans = min_depth_func(A) - 1 # 根は0としてカウントするようなので、-1する
print(ans)

A = Tree(1)
B = Tree(2)
C = Tree(3)
D = Tree(4)
E = Tree(5)
F = Tree(6)
A.children.append(B)
B.children.append(C)
C.children.append(D)
D.children.append(E)
E.children.append(F)
ans = min_depth_func(A) - 1
print(ans)

Comments

[aya0425]

ご回答いただきありがとうございます。
ご提示いただいたコードの
if tree.num_children() == 0:
return 1
のreturnを0にしたところ望んでいた結果を得られました。
コード内容もしっかり理解できました。大変助かりました！

Answer 3

全体的にうまくコード化できていません。
以下の概念コードを参考にしてみてください。

def min_depth_func(tree, 現在の階層位置):
    if tree.num_children() == 0:
        return 現在の階層位置

    for kid in tree.children:
        子供の結果 = min_depth_func(kid, 現在の階層位置＋１)

    return min(子供たちの結果)

Comments

[aya0425]

ご回答いただきありがとうございます。
追記で恐縮ですが、引数はtreeのみとのことです。
私の力不足で申し訳ないのですが、より詳細なご回答をいただけると大変嬉しいです。

[8524ba23]

ツリーノード自身が階層位置に関する情報を持っていれば引数で指定する必要はありません。
また、現状の再帰（深さ優先）処理ではなく幅優先で処理すれば同じく引数はtreeのみで実現できます。
課題のようなので、あとはご自身で頑張ってみてください。

[aya0425]

追加のご回答ありがとうございます。ご指摘いただいた内容を踏まえて理解を深めていけるよう努力します。