ありうる全ての二分探索木を求めるアルゴリズムで行き詰まりました

Question

二分探索木の勉強中です。
整数１からnの値を、各ノードの値とする二分探索木をリストで全て書き出すと言う問題で行き詰まりました。
理解できないのは以下のコードの一番最後の部分#####です。

from __future__ import annotations
from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        if n == 0:
            return []
        return self.generate(1, n)
    
    def generate(self, start, end):
        if start > end:
            return [None]
        
        all_trees = []
        # cnt = 0
        for currentRootVal in range(start, end + 1):
            all_left_subtrees = self.generate(start, currentRootVal - 1)
            all_right_subtrees = self.generate(currentRootVal + 1, end)
            for left_subtree in all_left_subtrees:
                for right_subtree in all_right_subtrees:
                    currentRoot = TreeNode(currentRootVal)
                    currentRoot.left = left_subtree
                    currentRoot.right = right_subtree
                    
                    all_trees.append(currentRoot) ##### 
                    # cnt += 1
                    # print(f"{cnt=}")
        return all_trees

if __name__ == "__main__":
    sol = Solution()
    f = sol.generateTrees(3)

他の部分の再帰の形は理解できましたが、二分木の全体のリストall_treesを作っている部分がわかりません。
二重ループで再帰的に二分木を作っている過程で毎回all_treesにappendしていますが、
このコードが再帰的に実行されることで、なぜうまく全ての木を網羅できるのでしょう。
再帰的に実行されることで、その過程で作られる未完成の木もappendされてしまうような気がしてなりません。
コメントアウトしていますが、cntという変数でappendの回数を数えましたが、例えばn=3の時は正しく５回と表示されます。
しかし、print(cnt)は15回実行され、cnt=1は９回表示されます。
再帰の理解不足ということはわかりますが、そこから理解が進まなくなりました。
参考までにn=3のときに返されるall_treesは、

[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

です。
説明が不十分かもしれませんが、よろしくお願いします。

Answer 1

回答が付かないようなので、回答してみます。

再帰の形は理解できたとのことですが、「二重ループで再帰的に二分木を作っている」わけではありませんが、そこの理解が違うのではないでしょうか。

最初のループ「for currentRootVal in range(start, end + 1):」でリストにあるすべての数字がrootであった場合をそれぞれ求め、結果をall_treesにappendしています。

以下のような感じです。

リストが 1～9で、 あるとき、rootに4が選ばれていたとしましょう。
このときでき求める二分木はどのようなものかと言うと、
(1) 4の左の枝には、1～3のリストで作られるものが付き、
(2) 4の右の枝には、5～9のリストで作られるものが付いたもの
です。
1と2がそれぞれ1通りずつであれば、それを付けたものですが、複数あるのであれば、それらをすべて組合せたものが答えになります。

ここまで判っていれば、コードは理解できると思いますが、
(1) が all_left_subtrees のことで、(2)が all_right_subtreesのことであり、以下にある二重ループは、それぞれの組合せて必要な二分木を生成しながらall_treesにappendしている処理です。

そして、(1)と(2)の処理はそれぞれが、元の問題と同じものなので、再帰呼び出しによって処理されています。