跳转至

783. 二叉搜索树节点最小距离

最后更新：2024-05-10-22

链接：https://leetcode.cn/problems/minimum-distance-between-bst-nodes/description/

题目描述

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

题目示例

输入： root = [4,2,6,1,3]

输出： 1

输入： root = [1,0,48,null,null,12,49]

输出： 1

提示：

思路

首先要想到二叉搜索树的特点，对于所有node，node->left以及子树的值都比node值小，node->right以及子树的值都比node值大。

对于node节点，满足题目条件的只有以下几种情况：

  • node->left 或者 node->right 就是尾节点，后面再没有子树了，那么以node为根节点的二叉搜索树，满足题目条件的只有两个值，最最小即可；
    • node->val - node->left->val
    • node->right->val - node->val;
  • node->left 不是尾节点，根据二叉树的特点，与node差值最小的值只能是left子树中最右端的值，即：node->left->right.....->right->val;
  • 同样的，对于右侧子节点也是一样，与node差值最小的应该是node->right->left.........->left->val
C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/

// 二叉搜索树，左侧都比root小，右侧都比root大
// 找差值最小的，对root，就是找left->right或者right->left
int minDiffInBST(struct TreeNode* root)
{
    int tmp = INT_MAX;
    int left = INT_MAX;
    int right = INT_MAX;
    if (root == NULL) {
        return 0;
    }

    if (root->left != NULL) {
        struct TreeNode* node = root->left;
        while (node->right != NULL) {
            node = node->right;
        }
        left = root->val - node->val;
        tmp = minDiffInBST(root->left);
        if (tmp < left) {
            left = tmp; 
        }
    }

    if (root->right != NULL) {
        struct TreeNode* node = root->right;
        while (node->left != NULL) {
            node = node->left;
        }
        right = node->val - root->val;
        tmp = minDiffInBST(root->right);
        if (tmp < right) {
            right = tmp; 
        }
    }

    if (left > right) {
        return right;
    }

    return left;
}
Go
1