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.
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
The number of nodes in both trees is in the range [0, 2000].
-104 <= Node.val <= 104
# 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 recursion(self,root1,root2):
if root1 and root2:
new_node=TreeNode(root1.val+root2.val)
new_node.left=self.recursion(root1.left,root2.left)
new_node.right=self.recursion(root1.right,root2.right)
return new_node
elif root1:
return root1
elif root2:
return root2
else:
return None
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
return self.recursion(root1,root2)
입력을 예로 들어서 설명한다.
두 트리 모두 루트가 있으므로 root 1 and root2
에 의해
new_node=TreeNode(3)
이 생성된다.
왼쪽으로 가본다. 부모 노드(값 3)는 그 결괏값을 기다린다.
왼쪽으로 간 분기에서는 val = 1 + 3 = 4인 노드가 생성된다.
왼쪽으로 가본다. 부모 노드(값 4)는 그 결괏값을 기다린다.
왼쪽으로 간 분기에선 root2가 None
이다. 기저 조건에 의해 root1을 리턴한다.
4.root1의 노드 (값 5)는 리턴되어 기다리고 있던 부모노드의 왼쪽에 부착된다.
new_node.left=self.recursion(root1.left,root2.left)
3.의 분기에서 이번엔 오른쪽에 가본다. 부모노드는 그 결괏값을 기다린다. 오른쪽으로 간 분기에선 root1이 None
이다. 기저조건에 의해 root2를 리턴한다.
root2의 노드 (값 4)는 리턴되어 기다리고 있던 부모 노드의 오른쪽에 부착된다.
new_node.right=self.recursion(root1.right,root2.right)
3.의 분기가 모두 끝났으므로 노드 (값 4)를 리턴한다. 기다리고 있던 부모 노드 (루트노드. 값 3)은 해당 노드를 왼쪽에 부착한다.
(오른쪽도 동일한 처리이므로 이하 생략)
익숙해질 때까지 풀어봐야 할 듯...