[파이썬 알고리즘 인터뷰][BST] 이진 탐색 트리 노드 간 최소 거리

[파이썬 알고리즘 인터뷰][BST] 이진 탐색 트리 노드 간 최소 거리

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

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

문제 정의

두 노드간

책에서 구현된 코드

class Solution: prev = -sys.maxsize result = sys.maxsize # 재귀 구조 중위 순회 비교 결과 def minDiffInBST(self, root: TreeNode) -> int: if root.left: self.minDiffInBST(root.left) self.result = min(self.result, root.val - self.prev) self.prev = root.val if root.right: self.minDiffInBST(root.right) return self.result

기억해야할 기법

트리의 탐색 순서에 대해 고민할 것

이 문제도 중위순회를 이용한다는 접근을 못함 트리에서 탐색이 필요할 시, 탐색 순서를 먼저 고민해볼 필요가 있을듯

내가 구현한 코드

class Solution: min_val = sys.maxsize def minDiffInBST(self, root: TreeNode) -> int: if root: if root.right: r = root.right while r.left: r = r.left self.min_val = min(self.min_val, abs(r.val - root.val)) if root.left: l = root.left while l.right: l = l.right self.min_val = min(self.min_val, abs(l.val - root.val)) self.minDiffInBST(root.left) self.minDiffInBST(root.right) return self.min_val

속도에 차이는 없지만, 책에서 구현한 내용이 명료하고 깔끔하다

트리 문제에 대한 접근은 탐색 순서부터 시작해야겠다

from http://pythaac.tistory.com/125 by ccl(A) rewrite - 2021-08-04 20:26:13