【LeetCode】114. Flatten Binary Tree to Linked List 解答・解説【Python】

この記事は約3分で読めます。

 

問題

原文

Given the root of a binary tree, flatten the tree into a “linked list”:

  • The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The “linked list” should be in the same order as a pre-order traversal of the binary tree.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

 

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

 

内容

二分木rootが与えられます。木を連結リストにしてください。

・左側の子ノードは常にNullにし、右側の子ノードはTreeNodeクラスの右側の子ノードが、連結リストの次のノードを指してください。(うまく書けませんでした。二分木の左側の子ノードを右側の子ノードにつなげていくことで連結リストとすることを意味していると思います。)

・連結リストは二分木のpre-order travasalと同じ順序にしてください。(親ノード>左側の子ノード>右側の子ノードの順に走査すること)

 

※正しくない可能性があります。

方針

・解答1:再帰処理

解答

解答1:

 

・各ノードの右側の子ノード [1] を一時変数に保持

・各ノードの左側の子ノードを右側の子ノードに追加

・右側の子ノードの葉まで移り、保持していた子ノード[1]を追加

・ここまでの処理を関数内の処理として再度呼び出す。

 

参考:PYTHON Explained | recursion | faster than 99% | simple solution ^_^ – Flatten Binary Tree to Linked List – LeetCode

ものすごくわかりやすい解説を書いてくれている方がいた。図の説明がわかりやすすぎた。

image

 

 

解答2

 

 

補足・参考・感想

参考

 

前:82. Remove Duplicates from Sorted List II

次:

LeetCode 解答・解説記事一覧

コメント