[Leetcode] 530. Minimum Absolute Difference in BST (Easy)

概述

題目

https://leetcode.com/problems/minimum-absolute-difference-in-bst/
給一 Binary Search Tree (BST)，求其子點數值差最小者

心得

經典 Inorder BST 題

Inorder Traverse

思路

先將所有點值 Inorder 方式取出，且會由小到大，兩兩比較差值，取最小者

程式

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 取點值
        def trv(root):
            if root == None:
                return
            trv(root.left)
            self.arr.append(root.val)
            trv(root.right)
        self.arr = []
        trv(root)

        return min([self.arr[i]-self.arr[i-1] for i in range(1, len(self.arr))])

Complexity

Time Complexity: O(n)
每個子點經過一次

Space Complexity: O(n)
存點值 n 個點

Recursive

思路

from leetcoder289，Trverse 每個子點時，透過左小右大方式來夾擊，以夾出最小差值之結果

程式

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def compare(root, lo, hi):
            if root == None:
                return hi - lo
            left  = compare(root.left,  lo, root.val)
            right = compare(root.right, root.val, hi)
            return min(left, right)
        return compare(root, -float("inf"), float("inf"))