题目描述：

LeetCode 530. 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: There are at least two nodes in this BST.

题目大意：

给定一棵BST（二叉搜索树），节点值为非负整数，计算任意两节点差的绝对值的最小值。

注意：BST中至少存在两个节点

解题思路：

解法I 中序遍历（In-order Traverse）

中序遍历将BST中的节点按照递增顺序输出

Python代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.last = -0x80000000
        self.ans = 0x7FFFFFFF
        def inOrderTraverse(root):
            if not root: return
            inOrderTraverse(root.left)
            self.ans = min(self.ans, root.val - self.last)
            self.last = root.val
            inOrderTraverse(root.right)
        inOrderTraverse(root)
        return self.ans

解法II 递归

对于BST中的某节点N：

大于N的最小节点为其右孩子的“极左节点”

小于N的最大节点为其左孩子的“极右节点”

然后递归取最小值

Python代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        left, right = root.left, root.right
        ans = 0x7FFFFFFF
        if left:
            while left.right: left = left.right
            ans = min(root.val - left.val, self.getMinimumDifference(root.left))
        if right:
            while right.left: right = right.left
            ans = min(ans, right.val - root.val, self.getMinimumDifference(root.right))
        return ans

 

本文链接：http://bookshadow.com/weblog/2017/02/26/leetcode-minimum-absolute-difference-in-bst/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码