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

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

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

출처 : 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 과정이 다른 것은 복잡한 코드에서는 좋은 방법이 아니라 생각함 각 재귀의 연산속도가 다른 것은 알고리즘의 안정성에 유해할 수도 있음

from http://pythaac.tistory.com/114 by ccl(A) rewrite - 2021-08-03 16:00:21