ほぼ日刊競プロ leetcode　617. Merge Two Binary Trees

617. Merge Two Binary Trees

You are given two binary trees root1 and root2.Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.Return the merged tree.
Note: The merging process must start from the root nodes of both trees.

二つの二分木を足し合わせる．なにもついていない時はそのまま

考えたこと

二つの二分木を探索していき，ノードがない場合は同じ位置にあるもう一つの木のノードを返すようにし，二つとも同じものがある場合は値を足すようにする．TreeNodeで返す必要があるタメにコンストラクタで初期値を値として足す．再帰的に元々合ったmergeTreeを呼び出してTreeNodeを返してあげる．書きは根→左→右で探索しているのでPreorderの形となる．

# 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 not root1 :
           return root2
       if not root2 :
           return root1
       ans = TreeNode(root1.val+root2.val)
       ans.left = self.mergeTrees(root1.left,root2.left)
       ans.right = self.mergeTrees(root1.right,root2.right)
       return ans