[파이썬 알고리즘 인터뷰][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

• 속도에 차이는 없지만, 책에서 구현한 내용이 명료하고 깔끔하다
• 트리 문제에 대한 접근은 탐색 순서부터 시작해야겠다