ゼロから始めるLeetCode Day45 「1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day44「543. Diameter of Binary Tree」
次回
ゼロから始めるLeetCode Day46「406. Queue Reconstruction by Height」

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.

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/discuss/539484/Simple-clean-and-fast-Python-solution-7-lines-beats-92

この回答はqueを使って書いていますが、わかりやすくて良いですね。
速さも申し分ないですし、問題を自分の解けるような型に無理やりはめるのではなく、このような回答の仕方も覚えて切り替えられるようになれるともっと問題を解いてて楽しそうですね！

今回はここまで。お疲れ様でした。