#概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day36「155. Min Stack」
今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
問題
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をもうちょっと読み込んでみようと思います、お疲れ様でした。