ゼロから始めるLeetCode Day12 「617. Merge Two Binary Trees」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day11 「1315. Sum of Nodes with Even-Valued Grandparent」
次回
ゼロから始めるLeetCode Day13 「338. Counting Bits」

問題

617. Merge Two Binary Trees

難易度はeasyで、goodの数が多いですね。

与えられた二つの二分木のそれぞれの数値を足し、新しい木を返すという問題です。

以上のように、それぞれの一致する箇所の数値が足算された木がoutputとして返されていますね。

解法

考え方としてはどちらか一方のノードが存在しない場合はもう一方のノードを返し、両方のノードが存在しない場合はNoneを、そして両方のノードが存在する場合は数値を足す、というものです。

とりあえず網羅的に書いたのがこれです。

# 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 mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1 and not t2:
            return None
        if not t1:
            return t2
        if not t2:
            return t1
        if t1 and t2:
            ans = TreeNode(t1.val + t2.val)
            ans.left = self.mergeTrees(t1.left,t2.left)
            ans.right = self.mergeTrees(t1.right,t2.right)
            return ans
# Runtime: 92 ms, faster than 63.90% of Python3 online submissions for Merge Two Binary Trees.
# Memory Usage: 15.1 MB, less than 5.72% of Python3 online submissions for Merge Two Binary Trees.

もうちょっと簡略化してみようって書き直したのがこちら

# 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 mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1:
            return t2
        if not t2:
            return t1
        ans = TreeNode(t1.val + t2.val)
        ans.left = self.mergeTrees(t1.left,t2.left)
        ans.right = self.mergeTrees(t1.right,t2.right)
        return ans
        
# Runtime: 84 ms, faster than 94.01% of Python3 online submissions for Merge Two Binary Trees.
# Memory Usage: 14.9 MB, less than 5.72% of Python3 online submissions for Merge Two Binary Trees.

ムラがあるとはいえ速くなりました。