[파이썬 알고리즘 인터뷰][트리] 두 이진 트리 병합

[파이썬 알고리즘 인터뷰][트리] 두 이진 트리 병합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

문제 정의

로그 재정렬 기준

책에서 구현된 코드

class Solution: def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode: if t1 and t2: node = TreeNode(t1.val + t2.val) node.left = self.mergeTrees(t1.left, t2.left) node.right = self.mergeTrees(t1.right, t2.right) return node else: return t1 or t2

기억해야할 기법

return t1 or t2

둘 중 하나가 존재하면, 존재하는 객체 리턴 둘 다 존재하지 않는다면, None 리턴

재귀를 이용하여 리턴되는 노드가 left / right로 오는 형태

내가 구현한 코드

class Solution: def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode: def dfs(res: TreeNode, node1: TreeNode, node2: TreeNode): val1 = val2 = 0 node1_l = node1_r = node2_l = node2_r = None # 현재 노드의 값 계산 if node1: val1 = node1.val node1_l = node1.left node1_r = node1.right if node2: val2 = node2.val node2_l = node2.left node2_r = node2.right res.val = val1 + val2 # left / right 재귀 if node1_l or node2_l: res.left = res_l = TreeNode() dfs(res_l, node1_l, node2_l) if node1_r or node2_r: res.right = res_r = TreeNode() dfs(res_r, node1_r, node2_r) if root1 is None and root2 is None: return None result = TreeNode() dfs(result, root1, root2) return result

속도는 비슷하지만, 작성한 코드의 차이가 어마어마하다

리턴 방식이 신기하다 (or를 사용했는데 boolean이 아니다)

꼭 기억해야할 설계다

from http://pythaac.tistory.com/116 by ccl(A) rewrite - 2021-08-03 21:26:48