LeetCode 783. Minimum Distance Between BST Nodes

파이썬 알고리즘 인터뷰 53번(리트코드 783) Minimum Distance Between BST Nodes
https://leetcode.com/problems/minimum-distance-between-bst-nodes/

나의 풀이

# 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: Optional[TreeNode]) -> int:
        def right_min(root):
            if not root:
                return 0
            while root.left:
                root = root.left
            return root.val
        def left_max(root):
            if not root:
                return 0
            while root.right:
                root = root.right
            return root.val
        def helper(root):
            curr = float("inf")
            if root:
                if root.left:
                    curr = min(curr, root.val - left_max(root.left), helper(root.left))
                if root.right:
                    curr = min(curr, right_min(root.right) - root.val, helper(root.right))
            return curr
        return helper(root)

다른 풀이1(Recursive)

# 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:
    prev = -float("inf")
    result = float("inf")
    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

다른 풀이2(In-Order Traversals)

# 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: Optional[TreeNode]) -> int:
        prev = -float("inf")
        result = float("inf")
        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