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

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

---

출처 : 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)의 최대값 찾기