ch14-5(leetcode 617). 두 이진 트리 병합

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 617번 ( https://leetcode.com/problems/merge-two-binary-trees/ )

 

✅교재를 참고한 풀이

 

📌재귀

 

문제에서 주어진 기본함수를 재귀함수로 사용해서 문제를 푸는 방법이다. 

두 개의 트리를 합쳐야 하므로, 재귀함수에서는 두 트리 각각의 노드 하나씩을 입력으로 받는다. 

 

만약 두 트리 모두 노드가 있다면 두 노드값의 합을 값으로 가진 노드를 리턴한다. 

if root1 and root2:
    node = TreeNode(root1.val+root2.val)

 

노드를 리턴하기 전, 자식 노드들에 대해서도 새 값을 가진 TreeNode를 할당해 주어야 한다. 

왼쪽, 오른쪽 자식 노드에 대해서 각각 재귀함수를 호출해서 TreeNode를 계산해 준 다음에 값을 리턴한다. 

node.left = self.mergeTree(root1.left, root2.left)
node.right = self.mergeTree(root1.right, root2.right)

return node

 

두 트리 중 하나의 노드만 있다면 해당 노드를 리턴한다. 

해당 코드의 경우, 두 트리의 노드가 모두 없을 때에는 None을 리턴하게 된다.

else:
    return root1 or root2

 

 

💡post-order traversal(후위 순회)

 

코드가 실행되는 순서는 다음과 같다.

1. 현재 노드의 값(두 트리를 합쳤을 때 현재 노드의 위치에 오는 값) 계산

2. 현재 노드의 왼쪽 subtree들의 값 계산

3. 현재 노드의 오른쪽 subtree들의 값 계산

 

그러나 실제로는 2번과 3번(left subtree, right subtree의 값)이 계산된 후에야 parent 노드의 값이 계산되므로, 이 재귀함수는 postorder(후위 순회) 방식으로 탐색한다. 

 

후위 순회 방식에서는 다음 순서로 탐색한다. 

1. 노드의 left subtree

2. 노드의 right subtree

3. 노드 자신