[파이썬 알고리즘 인터뷰][트리] 이진 트리의 직경

[파이썬 알고리즘 인터뷰][트리] 이진 트리의 직경

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

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

문제 정의

이진 트리에서 두 노드의 가장 긴 경로 길이 출력

책에서 구현된 코드

class Solution: longest: int = 0 def diameterOfBinaryTree(self, root: TreeNode) -> int: def dfs(node: TreeNode) -> int: if not node: return -1 # 왼쪽, 오른쪽 각각 리프 노드까지 탐색 left = dfs(node.left) right = dfs(node.right) # 가장 긴 경로 self.longest = max(self.longest, left + right + 2) # 상태값 return max(left, right) + 1 dfs(root) return self.longest

기억해야할 기법

class 변수 활용 함수의 global 변수로 global optimum 업데이트

내가 구현한 코드

def diameterOfBinaryTree(root: TreeNode) -> int: def dfs(node: TreeNode) -> (int, int): #(depth, max) # [1] left / right의 depth / max를 0으로 초기화 left_depth = right_depth = left_max = right_max = 0 # [2] left와 right 재귀 if node and node.left: left_depth, left_max = dfs(node.left) if node and node.right: right_depth, right_max = dfs(node.right) # [3] max는 left / right의 depth 합 this_max = left_depth + right_depth # [4] depth는 left / right의 depth중 큰 값 + 1 return max(left_depth, right_depth)+1, max(this_max, left_max, right_max) return dfs(root)[1]

속도는 역시 비슷하지만, 내가 구현한 코드가 공간을 더 사용하고 가독성도 떨어진다

문제 접근은 비슷하지만, 풀이 과정이 다름 내가 구현한 코드는 다음 두가지를 나눔

1) 서브트리가 만드는 최대 경로 길이

2) 현재 노드를 루트로 경유하여 만들 수 있는 최대 경로 길이

3) left의 1), right의 1), 그리고 2)를 비교하여 최대값 구하기 그러나 책에서 구현한 코드는 깔끔하게 만듦

- 각 노드에 대한 2)의 최대값 찾기

from http://pythaac.tistory.com/113 by ccl(A) rewrite - 2021-08-03 16:26:16