文章
341
粉丝
0
获赞
3
访问
32.0k
由于二叉搜索树的中序遍历序列为递增序列,本算法采用中序递归遍历二叉树,并记录当前找到的最小绝对值差值 min。
遍历过程中,每访问一个结点时计算目标值与当前结点值之差的绝对值:
min,则更新 min;min,说明后续结点的差值会更大,此时可停止查找(可通过标志变量 flag 控制递归终止)。
// 当前的绝对值差值最小值
int min = INT_MAX;
// 最小绝对值差值是否已经找到
int flag = 0;
// 存储待输出的结点关键字
int min_data[2];
int min_idx = 0;
void searchMinDiff(BTNode *root, int K) {
if (!root) return;
if (flag) return;
searchMinDiff(root->left, K);
// 中序遍历
int diff = abs(K - root->data);
if (diff < min) {
min = diff;
min_data[0] = root->data;
min_idx = 1;
} else if (diff == min) {
min_data[min_idx++] = root->data;
} else {
flag = 1;
}
searchMinDiff(root->right, K);
}
void solve(BTNode *root, int K) {
searchMinDiff(root, K);
printf("min diff: %d\n", min);
for (int i = 0; i < min_idx; i++) {
printf("min element: %d\n", min_data[i]);
}
}
登录后发布评论
暂无评论,来抢沙发