質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

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

fu_3823
fu_3823

総合スコア79

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

1回答

0グッド

2クリップ

817閲覧

投稿2021/08/19 21:03

編集2021/08/20 00:30

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

Pyhton

1from __future__ import annotations 2from typing import List, Optional 3 4# Definition for a binary tree node. 5class TreeNode: 6 def __init__(self, val=0, left=None, right=None): 7 self.val = val 8 self.left = left 9 self.right = right 10 11class Solution: 12 def generateTrees(self, n: int) -> List[Optional[TreeNode]]: 13 if n == 0: 14 return [] 15 return self.generate(1, n) 16 17 def generate(self, start, end): 18 if start > end: 19 return [None] 20 21 all_trees = [] 22 # cnt = 0 23 for currentRootVal in range(start, end + 1): 24 all_left_subtrees = self.generate(start, currentRootVal - 1) 25 all_right_subtrees = self.generate(currentRootVal + 1, end) 26 for left_subtree in all_left_subtrees: 27 for right_subtree in all_right_subtrees: 28 currentRoot = TreeNode(currentRootVal) 29 currentRoot.left = left_subtree 30 currentRoot.right = right_subtree 31 32 all_trees.append(currentRoot) ##### 33 # cnt += 1 34 # print(f"{cnt=}") 35 return all_trees 36 37if __name__ == "__main__": 38 sol = Solution() 39 f = sol.generateTrees(3)

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

Pyton

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

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

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

回答1

0

ベストアンサー

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

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

最初のループ「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)の処理はそれぞれが、元の問題と同じものなので、再帰呼び出しによって処理されています。

投稿2021/08/20 06:27

TakaiY

総合スコア10545

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。