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()でのキーの追加をするところでリストが分岐されていかないようです。リストオブジェクトの性質による動きなのでしょうか。
回答1件
あなたの回答
tips
プレビュー