当前位置： 面试刷题>> 二叉搜索树的最小绝对差(经典算法150题)
### 题目描述
给定一个二叉搜索树（BST），请找出树中任意两个节点的值之间的最小绝对差。
### 示例
假设给定的BST如下：
```
4
/ \
2 6
/ \
1 3
```
在这个BST中，节点值分别为 1, 2, 3, 4, 6。任意两个节点值之间的最小绝对差是 1，比如节点 2 和 3。
### 解题思路
由于BST的性质（左子树的所有节点的值都小于根节点的值，右子树的所有节点的值都大于根节点的值），我们可以使用中序遍历（左-根-右）来获取一个递增的节点值序列。然后，遍历这个序列，计算相邻节点之间的绝对差，找到最小值即可。
### PHP 示例代码
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function minDiffInBST($root) {
$values = [];
inorderTraversal($root, $values);
$minDiff = PHP_INT_MAX;
for ($i = 1; $i < count($values); $i++) {
$diff = $values[$i] - $values[$i - 1];
$minDiff = min($minDiff, $diff);
}
return $minDiff;
}
function inorderTraversal($node, &$values) {
if ($node === null) return;
inorderTraversal($node->left, $values);
$values[] = $node->val;
inorderTraversal($node->right, $values);
}
// 示例用法
$root = new TreeNode(4);
$root->left = new TreeNode(2);
$root->right = new TreeNode(6);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(3);
echo minDiffInBST($root); // 输出 1
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def minDiffInBST(root):
values = []
def inorder(node):
if not node:
return
inorder(node.left)
values.append(node.val)
inorder(node.right)
inorder(root)
min_diff = float('inf')
for i in range(1, len(values)):
min_diff = min(min_diff, values[i] - values[i-1])
return min_diff
# 示例用法
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(minDiffInBST(root)) # 输出 1
```
### JavaScript 示例代码
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function minDiffInBST(root) {
const values = [];
function inorder(node) {
if (!node) return;
inorder(node.left);
values.push(node.val);
inorder(node.right);
}
inorder(root);
let minDiff = Infinity;
for (let i = 1; i < values.length; i++) {
minDiff = Math.min(minDiff, values[i] - values[i - 1]);
}
return minDiff;
}
// 示例用法
const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(6);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
console.log(minDiffInBST(root)); // 输出 1
```
以上示例展示了如何在不同编程语言中实现二叉搜索树的最小绝对差算法。