概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day44「543. Diameter of Binary Tree」
今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
問題
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
難易度はMedium。
originalとclonedの2つのバイナリツリーが与えられ、originalのtargetへの参照が与えられます。
複製されたツリーは、元のツリーのコピーで、複製されたツリー内の同じノードへの参照を返します。
2つのツリーまたはtargetを変更することは許可されておらず、回答はclonedされたツリー内のノードへの参照でなければなりません。
フォローアップ：ツリーで繰り返し値が許可されている場合は、問題を解決してください。
解法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
if not original:
return None
if original == target:
return cloned
return self.getTargetCopy(original.left,cloned.left,target) or self.getTargetCopy(original.right,cloned.right,target)
# Runtime: 672 ms, faster than 60.93% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
# Memory Usage: 23.5 MB, less than 100.00% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
以上のような解き方をしました。
シンプルに書けたので比較的良い解答なのかと思ったのですが、そこまで速度が出ていないので他の解答を調べてみました。
class Solution:
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
que = collections.deque([(original, cloned)]) # start at the root
while que:
nodeOrig, nodeClon = que.popleft()
if nodeOrig is target: # if original node is found - cloned node is our answer
return nodeClon
if nodeOrig.left: que.append((nodeOrig.left, nodeClon.left))
if nodeOrig.right: que.append((nodeOrig.right, nodeClon.right))
# Runtime: 656 ms, faster than 92.51% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
# Memory Usage: 23.6 MB, less than 100.00% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
この回答はqueを使って書いていますが、わかりやすくて良いですね。
速さも申し分ないですし、問題を自分の解けるような型に無理やりはめるのではなく、このような回答の仕方も覚えて切り替えられるようになれるともっと問題を解いてて楽しそうですね！
今回はここまで。お疲れ様でした。