题目描述：
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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
