LeetCode: 530. Minimum Absolute Difference in BST

题目

原题地址：https://leetcode.com/problems/minimum-absolute-difference-in-bst/

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note:

解法

中序遍历生成数组，找出数组中所有相邻元素的差值的最小值

通过 BST 的特性可以知道，中序遍历 BST 生成的所有节点的值组成的数组会是一个从小到大不包含重复值的有序数组，因此节点间差的绝对值的最小值 只会在数组的相邻元素间产生，只需要找到这个最小的差值即可。

中序遍历的 Python 代码类似这样:

def inorder(root):
    if root is None:
        return
    inorder(root.left)

    # print(root)

    inorder(root.right)

这个方法的 Python 代码类似下面这样:

# 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):
        self.node_vals = []
        self.inorder(root)

        min_diff = None
        pre = None
        for v in self.node_vals:
            if pre is not None:
                diff = v - pre
                if min_diff is None:
                    min_diff = diff
                else:
                    min_diff = min(min_diff, diff)
            pre = v

        return min_diff


    def inorder(self, root):
        if root is None:
            return

        self.inorder(root.left)

        self.node_vals.append(root.val)

        self.inorder(root.right)

中序遍历直接找出节点间差的绝对值的最小值

上面的方法中的数组其实可以不需要生成，直接在中序遍历的过程中进行相应的计算也可以。

相应的 Python 代码类似下面这个:

# 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):
        self.min_diff = None
        self.pre_val = None
        self.inorder(root)
        return self.min_diff

    def inorder(self, root):
        if root is None:
            return

        self.inorder(root.left)

        if self.pre_val is not None:
            diff = root.val - self.pre_val
            if self.min_diff is None:
                self.min_diff = diff
            else:
                self.min_diff = min(self.min_diff, diff)

        self.pre_val = root.val

        self.inorder(root.right)

Comments