使用java语言:给定具有非负值的二叉搜索树,找到任意两个节点的值之间的最小绝对差值.
时间: 2023-05-22 18:05:48 浏览: 73
可以使用中序遍历二叉搜索树来得到一个有序的节点值序列,然后依次计算相邻节点值之间的绝对差值,取其中的最小值即为所求。例如:
public class Solution {
private int prev = -1; // 记录上一个遍历到的节点值
private int minDiff = Integer.MAX_VALUE; // 记录最小绝对差值
public int getMinimumDifference(TreeNode root) {
inorder(root);
return minDiff;
}
private void inorder(TreeNode node) {
if (node == null) {
return;
}
inorder(node.left);
if (prev != -1) { // 不是第一个节点
minDiff = Math.min(minDiff, node.val - prev);
}
prev = node.val; // 更新上一个节点值
inorder(node.right);
}
}
相关问题
给定具有非负值的二叉搜索树,找到任意两个节点的值之间的最小绝对差值.
可以使用中序遍历来得到二叉搜索树中节点值的有序序列,然后依次计算相邻两个节点值之间的差值,最终得到最小的差值即为所求的最小绝对差值。以下是示例代码:
```
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` 表示当前已计算的最小绝对差值。在每次遍历时,先递归遍历当前节点的左子树,然后与前一个节点的值计算差值,更新最小绝对差值和前一个节点的值,最后递归遍历当前节点的右子树。
C语言实现:给定一棵二叉搜索树的先序遍历序列,要求找到任意两结点的最近公共祖先结点
要实现这个功能,可以采用二叉搜索树的特性,即左子树中所有节点的值小于根节点的值,右子树中所有节点的值大于根节点的值。因此,在先序遍历序列中,根节点的值必定是序列的第一个元素。
具体的实现步骤如下:
1. 定义一个二叉树的结构体,包含键值和左右子节点指针。
2. 定义一个函数,输入先序遍历序列和序列长度,返回根节点。
3. 从先序遍历序列中取出第一个元素作为根节点。
4. 遍历序列,将小于根节点值的元素放入左子树序列,大于根节点值的元素放入右子树序列。
5. 递归创建左右子树,并将左右子树的根节点分别挂在根节点的左右子节点上。
6. 采用递归的方式遍历二叉树,查找节点U和V的位置。
7. 如果当前节点为NULL或者等于U或V,则返回当前节点。
8. 如果U和V分别在当前节点的左右子树中,则当前节点为最近公共祖先。
9. 如果U和V在当前节点的同一子树中,则继续向下递归。
10. 最终返回最近公共祖先节点的键值即可。
下面是实现代码的示例:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node* left;
struct Node* right;
} Node;
Node* create_bst(int* preorder, int len) {
if (len == 0) {
return NULL;
}
Node* root = (Node*) malloc(sizeof(Node));
root->key = preorder[0];
int i;
for (i = 1; i < len; i++) {
if (preorder[i] > root->key) {
break;
}
}
root->left = create_bst(preorder + 1, i - 1);
root->right = create_bst(preorder + i, len - i);
return root;
}
Node* find_lca(Node* root, int u, int v) {
if (root == NULL || root->key == u || root->key == v) {
return root;
}
if (u < root->key && v < root->key) {
return find_lca(root->left, u, v);
} else if (u > root->key && v > root->key) {
return find_lca(root->right, u, v);
} else {
return root;
}
}
int main() {
int preorder[] = {6, 2, 1, 4, 3, 5, 9, 7, 10};
int len = sizeof(preorder) / sizeof(preorder[0]);
Node* root = create_bst(preorder, len);
int u = 3, v = 5;
Node* lca = find_lca(root, u, v);
printf("LCA of %d and %d is %d\n", u, v, lca->key);
u = 4, v = 9;
lca = find_lca(root, u, v);
printf("LCA of %d and %d is %d\n", u, v, lca->key);
u = 4, v = 5;
lca = find_lca(root, u, v);
printf("LCA of %d and %d is %d\n", u, v, lca->key);
return 0;
}
```
输出结果如下:
```
LCA of 3 and 5 is 4
LCA of 4 and 9 is 6
LCA of 4 and 5 is 4
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)