ゼロから始めるLeetCode Day37「105. Construct Binary Tree from Preorder and Inorder Traversal」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day36「155. Min Stack」
次回
ゼロから始めるLeetCode Day38「208. Implement Trie (Prefix Tree)」

問題

105. Construct Binary Tree from Preorder and Inorder Traversal

難易度はMedium。
Top 100 Liked Questionsからの抜粋です。
前回でEasyが全て解き終わったので今回からはMediumを解いていきます。

問題としては、木の構造として、inorderとpreorderが引数として与えられるので、それらを元に二分木を構築するようなアルゴリズムを書いてください、というものです。

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

解法

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None
        
        preordersIndex = preorder[0]
        Tree = TreeNode(preordersIndex)
        inordersIndex = inorder.index(preordersIndex)
        
        Tree.left = self.buildTree(preorder[1:inordersIndex+1],inorder[:inordersIndex])
        Tree.right = self.buildTree(preorder[inordersIndex+1:],inorder[inordersIndex+1:])
        return Tree
# Runtime: 216 ms, faster than 33.07% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
# Memory Usage: 87.7 MB, less than 13.16% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

再帰で解きました。TreeNodeのroot部分は固定になるので先に代入しておき、あとはTreeを左と右に分けて再帰で代入し続けました。

ちなみに、こうやって書くよりも短く書かれていたのがdiscussにあったのでこちらも載せておきます。

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root
# Runtime: 164 ms, faster than 49.71% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
# Memory Usage: 52.2 MB, less than 60.53% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

読みやすい上に速い・・・！
この解答を載せている人はどの問題でも大体簡潔なコードをPythonで書いているのでとても参考になります。

Easyまでは一つの要素についての処理ができれば大体解けていたのですが、Mediumだと二つ以上の要素を上手く処理することを求められるイメージですね。
もっと精進せねば。

他にもdiscussをもうちょっと読み込んでみようと思います、お疲れ様でした。