二叉搜索树最小差值

[编程题]二叉搜索树最小差值

热度指数：1425 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉搜索树，请你返回树中任意两节点之差的最小值。

数据范围：二叉树节点数满足 $2 \le n \le 10^5 \$ ，二叉树的节点值满足 $0 \le val \le 10^9 \$ ，保证每个节点的值都不同

示例1

输入

{2,1,3,#,#,#,4}

输出

示例2

输入

{3,1,5,#,#,#,9}

输出

备注:

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

可以叫我啊星

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

int MIN(int a, int b) {

return a < b? a:b;

}

void dfs(struct TreeNode* root, int* arr, int *size){

if(root == NULL)

return ;

dfs(root->left, arr, size);

arr[(*size)++] = root->val;

dfs(root->right, arr, size);

}

int minDifference(struct TreeNode* root) {

// write code here

if(root == NULL)

return 0;

int size = 0;

int *res = (int*)calloc(pow(10, 5), sizeof(int));

dfs(root, res, &size);

int min_val = res[1] - res[0];

for(int i = 1; i < size; i++)

min_val = MIN(min_val, res[i] - res[i-1]);

return min_val;

}

发表于 2025-05-14 15:11:49 回复(0)

猪猪侠新新酱

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return int整型
 */
int preorder(struct TreeNode* root, int* arr) {
    static int count = 0;
    if (NULL != root) {
        arr[count++] = root->val;
        preorder(root->left, arr);
        preorder(root->right, arr);
    }
    return count;
}
int cnp(const void* e1,const void *e2){
    return *(int*)e1-*(int*)e2;
}
int minDifference(struct TreeNode* root ) {
    // write code here
    int* arr=(int *)malloc(sizeof(int)*100000);
    int count=preorder(root, arr);
    qsort(arr,count,sizeof(int),cnp);
    int ans=1000000000;
    for(int i=1;i<count;i++){
          if(ans>(arr[i]-arr[i-1]))
              ans=arr[i]-arr[i-1];
    }
    return ans;
}

发表于 2023-01-10 16:35:29 回复(0)