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

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

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

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

Python

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

Q&A

解決済

1回答

732閲覧

二分木を再帰でトラバースするとき、Pythonのリストの挙動がうまく理解できない

fu_3823

総合スコア81

アルゴリズム

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

Python

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

0グッド

0クリップ

投稿2022/04/15 13:16

編集2022/04/16 06:45

LeetCodeで以下の問題を解いています。
257. Binary Tree Paths
問題は、与えられた二分木の根から葉までの全てのパスを網羅して表示するものです。
問題自体は難しくはありませんが、再帰でパスを辿る時に、リストを使うとうまくいきません。
以下のコードで、lはリストsが文字列として、ノードのキーを追加しながら辿っていきます。しかし、文字列の方はうまくパスを網羅できるのに対して、リストでは同じようにいきません。
どうしてでしょうか。

Pyhton

1def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: 2 l = [] 3 s = "" 4 res = [] 5 def helper(root, l, s): 6 if root: 7 l.append(str(root.val))   # パスをリストで表現 8 s += str(root.val)     # パスを文字列で表現 9 print('lst:', l, 'string:', s, '\n') # パスを表示 10 if not root.left and not root.right: 11 res.append(l) 12 res.append(s) 13 else: 14 helper(root.left, l, s) 15 helper(root.right, l, s) 16 17 helper(root, l, s) 18 return res

上記のコードは、リストと文字列の両方でテストしているのと、解答の書式に合っていないので、正解にはなりませんが、以下のような結果になります。二分木のイメージは、リンクを参照していただけると助かります。
入力
[1,2,3,null,5]
出力
リストを使った時 [["1","2","5","3"], ["1","2","5","3"]]
文字列を使った時 [,"125", "13"]

リストを使うと、二分木の分岐で再起の際、List.append()でのキーの追加をするところでリストが分岐されていかないようです。リストオブジェクトの性質による動きなのでしょうか。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Sobasenbei

2022/04/15 16:40 編集

上手くいかないとは具体的にどのような結果にになっているのでしょうか?
fu_3823

2022/04/15 20:40

すみません。コード下のパラグラフが抜けていました。更新前の、記事を投稿してしまいました。 申し訳ありません。 訂正しましたので、ご確認お願いします。
guest

回答1

0

ベストアンサー

listがミュータブルで、appendがlistを直接書き換えるからです。

以下のコードを実行すると、['a','b']と表示されます。関数内でappendすると、引数として渡したlistが直接書き換えられるので、呼び出し元のlistも書き換わってしまいます。

python

1def f(l): 2 l.append('b') 3l=['a'] 4f(l) 5print(l)

次に、以下のコードを実行すると、aと表示されるはずです。strはミュータブルではないので、関数内で+=しても、strが書き換えられるのではなく、新たなstrを生成してそれを代入するという動作となります。

python

1def g(s): 2 s += 'b' 3s='a' 4g(s) 5print(s)

呼び出し元を書き換えたくないなら、+で明示的に新たなlistを生成するようにしましょう(+=だと直接書き換えられてしまうので注意)。以下のコードなら['a']と表示されるはずです。

python

1def f(l): 2 l = l + ['b'] 3l=['a'] 4f(l) 5print(l)

こちらの公式のFAQが参考になるかもしれません。
なぜ list 'y' を変更すると list 'x' も変更されるのですか?

投稿2022/04/16 01:58

actorbug

総合スコア2212

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問