博文中会简要介绍Leetcode P0270题目分析及解题思路。
“Closest Binary Search Tree Value”是一道较为简单的题目，直接利用二叉搜索即可。
Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int closestValue(TreeNode root, double target) {
this.dfs(root, target, Double.MAX_VALUE);
return this.closest;
}
private int closest = 0;
private void dfs(TreeNode curr, double T, double D) {
if (curr == null)
return;
double diff = Math.abs(curr.val-T);
if (D > diff) {
D = diff;
this.closest = curr.val;
}
if (curr.val > T)
this.dfs(curr.left, T, D);
else if (curr.val < T)
this.dfs(curr.right, T, D);
return;
}
}
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int closestValue(TreeNode* root, double target) {
_Dfs(root, target, DBL_MAX);
return _closest;
}
private:
int _closest = 0;
void _Dfs(TreeNode *cur, double t, double D) {
if (!cur)
return;
double diff = abs(cur->val-t);
if (D > diff) {
D = diff;
_closest = cur->val;
}
if (cur->val > t)
_Dfs(cur->left, t, D);
else if (cur->val < t)
_Dfs(cur->right, t, D);
return;
}
};