[알고리즘] 이진 탐색 트리(BST) 노드 간 최소 거리

이진 탐색 트리(BST) 노드 간 최소 거리

책 풀이

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 TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        prev = -sys.maxsize
        result = sys.maxsize

        stack = []
        node = root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left

            node = stack.pop()

            result = min(result, node.val - prev)
            prev = node.val

            node = node.right

        return result

스택을 이용한 DFS 풀이이다.