Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
- Given target value is a floating point.
- You are guaranteed to have only one unique value in the BST that is closest to the target.
这道题让我们找一个二分搜索数的跟给定值最接近的一个节点值，由于是二分搜索树，所以我最先想到用中序遍历来做，一个一个的比较，维护一个最小值，不停的更新，实际上这种方法并没有提高效率，用其他的遍历方法也可以，参见代码如下：
解法一：
class Solution { public: int closestValue(TreeNode* root, double target) { double d = numeric_limits<double>::max(); int res = 0; stack<TreeNode*> s; TreeNode *p = root; while (p || !s.empty()) { while (p) { s.push(p); p = p->left; } p = s.top(); s.pop(); if (d >= abs(target - p->val)) { d = abs(target - p->val); res = p->val; } p = p->right; } return res; } };
实际我们可以利用二分搜索树的特点(左<根<右)来快速定位，由于根节点是中间值，我们在往下遍历时，我们根据目标值和根节点的值大小关系来比较，如果目标值小于节点值，则我们应该找更小的值，于是我们到左子树去找，反之我们去右子树找，参见代码如下：
解法二：
class Solution { public: int closestValue(TreeNode* root, double target) { int res = root->val; while (root) { if (abs(res - target) >= abs(root->val - target)) { res = root->val; } root = target < root->val ? root->left : root->right; } return res; } };
以上两种方法都是迭代的方法，下面我们来看递归的写法，下面这种递归的写法和上面迭代的方法思路相同，都是根据二分搜索树的性质来优化查找，但是递归的写法用的是回溯法，先遍历到叶节点，然后一层一层的往回走，把最小值一层一层的运回来，参见代码如下：
解法三：
class Solution { public: int closestValue(TreeNode* root, double target) { int a = root->val; TreeNode *t = target < a ? root->left : root->right; if (!t) return a; int b = closestValue(t, target); return abs(a - target) < abs(b - target) ? a : b; } };
再来看另一种递归的写法，思路和上面的都相同，写法上略有不同，用if来分情况，参见代码如下：
解法三：
class Solution { public: int closestValue(TreeNode* root, double target) { int res = root->val; if (target < root->val && root->left) { int l = closestValue(root->left, target); if (abs(res - target) >= abs(l - target)) res = l; } else if (target > root->val && root->right) { int r = closestValue(root->right, target); if (abs(res - target) >= abs(r - target)) res = r; } return res; } };
最后来看一种分治法的写法，这种方法相当于解法一的递归写法，并没有利用到二分搜索树的性质来优化搜索，参见代码如下：
解法四：
class Solution { public: int closestValue(TreeNode* root, double target) { double diff = numeric_limits<double>::max(); int res = 0; helper(root, target, diff, res); return res; } void helper(TreeNode *root, double target, double &diff, int &res) { if (!root) return; if (diff >= abs(root->val - target)) { diff = abs(root->val - target); res = root->val; } helper(root->left, target, diff, res); helper(root->right, target, diff, res); } };
本文转自博客园Grandyang的博客，原文链接：最近的二分搜索树的值[LeetCode] Closest Binary Search Tree Value ，如需转载请自行联系原博主。
