给定具有非负值的二叉搜索树,找到任意两个节点的值之间的最小绝对差值.
时间: 2023-05-22 14:05:45 浏览: 63
可以使用中序遍历来得到二叉搜索树中节点值的有序序列,然后依次计算相邻两个节点值之间的差值,最终得到最小的差值即为所求的最小绝对差值。以下是示例代码:
```
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
int minDiff = INT_MAX;
int prevValue = -1;
inorderTraversal(root, prevValue, minDiff);
return minDiff;
}
void inorderTraversal(TreeNode* node, int& prevValue, int& minDiff) {
if (node == nullptr) {
return;
}
inorderTraversal(node->left, prevValue, minDiff);
if (prevValue != -1) {
minDiff = min(minDiff, node->val - prevValue);
}
prevValue = node->val;
inorderTraversal(node->right, prevValue, minDiff);
}
};
```
在以上代码中,`inorderTraversal` 函数用于实现中序遍历,`prevValue` 表示前一个节点的值,`minDiff` 表示当前已计算的最小绝对差值。在每次遍历时,先递归遍历当前节点的左子树,然后与前一个节点的值计算差值,更新最小绝对差值和前一个节点的值,最后递归遍历当前节点的右子树。