🎉

【LeetCode】617. Merge Two Binary Treesを解く

2021/02/21に公開

問題へのリンク

問題概要

2つの二分木root1root2が与えられる.これらの二分木を重ねて二分木を統合する事を考える.

統合のルール

  • 2つのノードが重なっているとき:ノードの値を足し合わせたものを新しいノードとする
  • 重なっていないとき:nullでは無いノードの値を新しいノードとする.

img

制約

  • 各二分木のノードの数:0 \leq N \leq 2000
  • -10^4 \leq Node.val \leq 10^4

考えたこと

方針としては,root1を修正・改変することでin-placeに答えを求める.

この問題では,

  1. 2つのnullでないノードが重なっている
  2. 1つのみnullでないノードが存在する
  3. 2つのノードがnull

の3つの状態がある.

まず,①の状態についてはnode1.val += node2.valという処理によって統合できる.

次に,②の状態についてはnode1 == null or node2 == nullの2つの状態が考えられ,nullでない方のノードを連結すれば良い.

最後に,③の状態について処理を考えたいところだが,②においてnullでないノードを連結することでそれ以降の処理は考えなくて済むことが分かる.

以上の方針に従って,再帰処理で実装したの回答が以下のコードである:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 is None:
            return t2
        elif t2 is None:
            return t1
        
        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)
        return t1

Discussion