🎉
【LeetCode】617. Merge Two Binary Treesを解く
問題概要
2つの二分木root1
,root2
が与えられる.これらの二分木を重ねて二分木を統合する事を考える.
統合のルール
- 2つのノードが重なっているとき:ノードの値を足し合わせたものを新しいノードとする
- 重なっていないとき:
null
では無いノードの値を新しいノードとする.
制約
- 各二分木のノードの数:
0 \leq N \leq 2000 -10^4 \leq Node.val \leq 10^4
考えたこと
方針としては,root1
を修正・改変することでin-placeに答えを求める.
この問題では,
- 2つの
null
でないノードが重なっている - 1つのみ
null
でないノードが存在する - 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