[LeetCode] 783. Minimum Distance Between BST Nodes [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Minimum Distance Between BST Nodes - LeetCode>

1. 문제 (이진 탐색 트리(BST) 노드 간 최소 거리)

두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라.

2. 풀이

재귀탐색과 중위순회를 이용한 풀이

반복문과 중위순회를 이용한 풀이

3. 코드

• 재귀탐색과 중위순회를 이용한 풀이

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    pre, ret = -100000, 100000
    def minDiffInBST(self, root: TreeNode) -> int:
        if root.left:
            self.minDiffInBST(root.left)

        self.ret = min(self.ret, root.val - self.pre)
        self.pre = root.val

        if root.right:
            self.minDiffInBST(root.right)

        return self.ret

• 반복문과 중위순회를 이용한 풀이

# Definition for a binary tree node.
# 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:
        pre, ret = -100000, 100000
        stack = []
        node = root

        while stack or node:
            while node:
                stack.append(node)
                node = node.left

            node = stack.pop()
            ret = min(ret, node.val - pre)
            pre = node.val
            node = node.right

• 결과 :

방식	Status	Runtime	Memory	Language
재귀탐색	[Accepted]	36 ms	14.3 MB	python3
반복문	[Accepted]	32 ms	14.3 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋