# 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:

## 解法¶

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

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

# print(root)

inorder(root.right)
```

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

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

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

comments powered by Disqus