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

概要

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

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day39「494. Target Sum」
次回
ゼロから始めるLeetCode Day41「394. Decode String」

Twitterやってます。

問題

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に次の要素を入れる、というものです。

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