题目描述：

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.

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
``````

```大于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
``````

Pingbacks已关闭。