問題
次のように定義される二分木を考える．
1
2
3
4
5
6
| # 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
|
2つの二分木root1/root2が与えられる．これらを重ねた結果得られる二分木を計算せよ．
例：
1
2
3
| 1 2 3
3 2 + 1 3 = 4 5
5 4 7 5 4 7
|
解法
mergeTree(root1, root2)はroot1を根とする木とroot2を寝とする木を重ねる関数- まず根（
root1/root2）を重ねる - 左右の部分木については再帰的に考えられる．つまり
mergeTree(root1.left, root2.left)はroot1.leftを根とする木とroot2.leftを寝とする木を重ねる関数mergeTree(root1.right, root2.right)はroot1.rightを根とする木とroot2.rightを寝とする木を重ねる関数- これらの結果が重ね終わった木の根の左右の部分木になってほしいのでつける．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| # 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, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if root1 is None:
return root2 # 相方がいなければ足さずににそのまま
if root2 is None:
return root1 # 相方がいなければ足さずにそのまま
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
|
出典