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

問題
1. 原文
2. 内容
方針
解答
1. 解答1：
2. 解答2
補足・参考・感想

問題

原文

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:

Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]

1
2

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = [] Output: []

1
2

Input: root = []
Output: []

Example 3:

Input: root = [0] Output: [0]

1
2

Input: root = [0]
Output: [0]

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：

# 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



#recursive
class Solution:        
    def flatten(self, root: Optional[TreeNode]) -> None:    
        if root:
            #右側の子ノードを保持
            temp = root.right
            
            #左側の子ノードを右側の子ノードに格納
            root.right = root.left
            #左側の子ノードをNoneに設定
            root.left = None

            #currentにrootノードを保持
            current = root
            #右側の子ノードの葉ノードを取得
            while current.right:
                #各ループで右側の子ノードを辿り続けている
                current = current.right
            #葉ノードにtempを格納(当初の右側の子ノード)
            current.right = temp

            #ここまでを再帰的に処理
            self.flatten(root.right)

# 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

#recursive

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

if root:

#右側の子ノードを保持

temp = root.right

#左側の子ノードを右側の子ノードに格納

root.right = root.left

#左側の子ノードをNoneに設定

root.left = None

#currentにrootノードを保持

current = root

#右側の子ノードの葉ノードを取得

while current.right:

#各ループで右側の子ノードを辿り続けている

current = current.right

#葉ノードにtempを格納(当初の右側の子ノード)

current.right = temp

#ここまでを再帰的に処理

self.flatten(root.right)

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

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

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

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

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

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

解答2

補足・参考・感想

参考

前：82. Remove Duplicates from Sorted List II

次：268. Missing Number

LeetCode 解答・解説記事一覧