跳转至

270. 最接近的二叉搜索树值

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

链接：https://leetcode.cn/problems/closest-binary-search-tree-value/description/

解题思路

首先必须了解二叉搜索树的特性

对于一个节点node，如果node->val > target，说明满足条件的值要么就是node->val，要么在node节点的左侧子节点上。

同样的，如果node->val < target，说明满足条件的值要么就是node->val，要么在node节点的右侧子节点上。

根据这个特性，我们利用递归，循环去找，一定能找到某两个节点满足题目条件，如下两种情况：

  • node->val > target node->left->val < target
  • node->val < target node->right->val > target

从找到的两个节点中，找到满足条件的值返回即可。

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
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/

int closestValue(struct TreeNode* root, double target)
{
    int left, right;
    if (root == NULL) {
        return 0;
    }

    // target 在左子节点
    // printf("val %d \n", root->val);
    if (root->val > target) {
        // 左子节点为空，返回root
        if (root->left == NULL) {
            return root->val;
        }

        // 继续往左，找到第一个比target小的节点，返回值
        left = closestValue(root->left, target);
        if ((root->val - target) > (target - left)) {
            return left;
        }
    } else {
        if (root->right == NULL) {
            return root->val;
        }

        // 继续往右，找到第一个比target大的节点，返回值
        right = closestValue(root->right, target);
        if ((target - root->val) > (right - target)) {
            return right;
        }
    }

    return root->val;
}
Go
1