[파이썬 알고리즘 인터뷰][트리] 가장 긴 동일 값의 경로

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

---

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

 

문제 정의

트리에서 노드가 갖는 값이 같은 경로의 최대 길이

 

책에서 구현된 코드

class Solution:
    result: int = 0

    def longestUnivaluePath(self, root: TreeNode) -> int:
        def dfs(node: TreeNode):
            if node is None:
                return 0

            # 존재하지 않는 노드까지 DFS 재귀 탐색
            left = dfs(node.left)
            right = dfs(node.right)

            # 현재 노드가 자식 노드와 동일한 경우 거리 1 증가
            if node.left and node.left.val == node.val:
                left += 1
            else:
                left = 0
            if node.right and node.right.val == node.val:
                right += 1
            else:
                right = 0

            # 왼쪽, 오른쪽 자식 노드간 거리의 합 최대값이 결과
            self.result = max(self.result, left + right)
            # 자식 노드 상태값 중 큰 값 리턴
            return max(left, right)

        dfs(root)
        return self.result

 

기억해야할 기법

• 조건부 누적값 / 초기화
  
  • 조건을 만족하면 if
  • 조건을 만족하지 않으면 else로 초기화
• 한 번의 로직으로 결과를 출력하도록 만들기
  • 처음 구현했던 코드는 노드의 개수를 구하는 로직이었음
    - 노드의 개수가 반환되면, 정답의 집합이 {0, 2, 3, 4, ...}이므로, 1에 대한 번거로운 처리를 해야함

 

내가 구현한 코드

# 책에서 구현한 알고리즘을 보고 수정한 코드
class Solution:
    longest = 0
    def longestUnivaluePath(self, root: TreeNode) -> int:
        def dfs(node: TreeNode):
            if not node:
                return 0

            # max_depth : 현재 노드가 루트일 때 최대 경로 길이
            # val_depth : 현재 노드가 루트일 때 최대 깊이 (같은 값만 해당)
            max_depth = val_depth = 0
            left = dfs(node.left)
            right = dfs(node.right)

            # max_depth = (left/right의 depth 합) + 1
            # val_depth = (left/right 중 큰 값) + 1
            if left > 0 and node.left.val == node.val:
                max_depth += left
                val_depth = left
            if right > 0 and node.right.val == node.val:
                max_depth += right
                val_depth = max(val_depth, right)

            # max_depth : 최대 길이 업데이트
            # val_depth : 현재 val에 대한 depth 반환
            self.longest = max(self.longest, max_depth)
            return val_depth + 1
        dfs(root)
        return self.longest
        
        
# 수정하기 전 코드
class Solution:
    longest = 0
    def longestUnivaluePath(self, root: TreeNode) -> int:
        def dfs(node: TreeNode):
            if not node:
                return 0

            # max_depth : 현재 노드가 루트일 때 최대 경로 길이
            # val_depth : 현재 노드가 루트일 때 최대 깊이 (같은 값만 해당)
            max_depth = val_depth = 1
            left = dfs(node.left)
            right = dfs(node.right)

            # max_depth = (left/right의 depth 합) + 1
            # val_depth = (left/right 중 큰 값) + 1
            if left > 0 and node.left.val == node.val:
                max_depth += left
                val_depth = left + 1
            if right > 0 and node.right.val == node.val:
                max_depth += right
                val_depth = max(val_depth, right+1)

            # max_depth : 최대 길이 업데이트
            # val_depth : 현재 val에 대한 depth 반환
            self.longest = max(self.longest, max_depth)
            return val_depth
        dfs(root)
        if self.longest > 0:
            self.longest -= 1
        return self.longest

• 책에서 구현한 알고리즘의 가독성이 매우 명확하고 좋음
  • 각 노드에서 어떤 재귀가 일어나는지 바로 인지할 수 있음
  • 재귀로 인한 값의 변화까지 명확함
  • 책에서 구현한 알고리즘을 보고 가독성을 위해 코드를 수정할 수 있었음
    - 노드의 개수가 아닌, 간선의 개수 중심으로 수정
• 내가 구현한 알고리즘 속도가 약간 더 빠름
  • 내 코드는 right와 val가 일치하지 않으면 비교연산(max)를 수행하지 않음
  • 책에서 구현한 코드는 left와 right의 무의미한 비교도 수행

• 그러나 책에서 구현한 코드처럼 구현해야함
  • 속도 차이 정도가 유의미한 결과는 아님
  • 가독성이 떨어짐
    - val_depth에 대한 left / right 과정이 다른 것은 복잡한 코드에서는 좋은 방법이 아니라 생각함
  • 각 재귀의 연산속도가 다른 것은 알고리즘의 안정성에 유해할 수도 있음