두 이진 트리 합치기 문제
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.
Example 1:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Example 2:
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
Constraints:
The number of nodes in both trees is in the range [0, 2000].
-104 <= Node.val <= 104
문제 해결 방법
이 문재는 재귀적인 개념을 활용하여 푸는 것이 코드의 간결성 측면에서 우월하다.
해결 방법
노드가 둘다 비어 있지 않은 경우 > 합치기
노드가 둘중 하나만 비어 있는 경우 > 해당 노드만 출력
노드가 둘다 비어 있는 경우 > None 출력
위의 과정만 지키면 된다.
구현은 아래와 같다.
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, t1, t2):
if t1 and t2:
root = TreeNode(t1.val + t2.val)
root.left = self.mergeTrees(t1.left, t2.left)
root.right = self.mergeTrees(t1.right, t2.right)
return root
else:
return t1 or t2
return t1 or t2는 둘중 True 인 녀석만 출력하는 녀석이다.
둘다 True인 경우 t1이 출력 되고, 둘다 False 인 경우 t2가 출력이 된다.
여기서 문제는 둘다 False인 경우인데 t1 t2 노드가 둘다 비어 있는 경우는 문제가 된다.
하지만 t2 역시 비어 있으므로 그냥 t2를 출력하면 되므로 따로 조건을 붙여줄 필요는 없다.
구체적으로 왼쪽 2 노드와 오른쪽 3 노드는 왼쪽 자식이 없다.
때문에 mergeTree(t1.left, t2.left)가 문제가 될 소지가 있다.
그러나 둘다 None이기 때문에 None을 리턴하여 root.left에 None을 입력해주기 때문에 적절해진다.
