ゼロから始めるLeetCode Day40「114. Flatten Binary Tree to Linked List」

#概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day39「494. Target Sum」

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

Twitterやってます。

40回目です。そろそろ辞め時が分からなくなってきました。

問題

114. Flatten Binary Tree to Linked List

難易度はMedium。
Top 100 Liked Questionsからの抜粋です。

二分木が与えられるので、フラットなリストに変換するようなアルゴリズムを設計してください。

これだけでは分かりづらいので例を見てみましょう。

    1
   / \
  2   5
 / \   \
3   4   6
The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

やはり例を見ると分かりやすいですね。

解法

# 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
class Solution:
    def flatten(self, root: TreeNode) -> None:
        prelevel = None
        """
        Do not return anything, modify root in-place instead.
        """
        def dfs(node):
            if node:
                dfs(node.right)
                dfs(node.left)
            
                nonlocal prelevel
                node.right = prelevel
                node.left = None
                prelevel = node
        
        dfs(root)
# Runtime: 36 ms, faster than 74.14% of Python3 online submissions for Flatten Binary Tree to Linked List.
# Memory Usage: 14.6 MB, less than 8.70% of Python3 online submissions for Flatten Binary Tree to Linked List.     

dfsで解きました。
prelevelで代入する要素を保持し、ひたすらnode.rightに要素を、node.leftにNoneを代入し、prelevelに次の要素を入れる、というものです。

良い感じの回答にまとまりました。
今回はこの辺で。お疲れ様でした。