5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-05-04

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

ゼロから始めるLeetCode 目次

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

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

問題

617. Merge Two Binary Trees

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

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

スクリーンショット 2020-05-04 9.08.45.png

以上のように、それぞれの一致する箇所の数値が足算された木が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.

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

5
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?