[코테] 리트코드 트리 783. Minimum Distance Between BST Nodes

783. Minimum Distance Between BST Nodes

문제 링크

https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/

문제 설명

Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.

제한 사항

• The number of nodes in the tree is in the range [2, 100].
• 0 <= Node.val <= 10^5

입출력 예 #1

1. Input : root = [4,2,6,1,3]
2. Output : 1

입출력 예 #2

1. Input : root = [1,0,48,null,null,12,49]
2. Output : 1

문제 풀이

1. 재귀 구조로 중위 순회
2. 반복 구조로 중위 순회

class Solution:
    prev = -sys.maxsize
    result = sys.maxsize

    # 재귀 구조 중위 순회 비교 결과
    def minDiffInBST(self, root: Optional[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:
    def minDiffInBST(self, root: Optional[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