[LeetCode] Closest Binary Search Tree Value-白红宇

[LeetCode] Closest Binary Search Tree Value

阅读量：6402 次

发布时间：2019-06-23

本文共 1361 字，大约阅读时间需要 4 分钟。

Problem Description:

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.

Well, this problem can be solved easily using recursion: just find the closest value in the left and right subtrees and compare them with root -> val. The code is as follows.

1 class Solution { 2 public: 3     int closestValue(TreeNode* root, double target) { 4         if (!root) return INT_MAX; 5         if (!(root -> left) && !(root -> right)) return root -> val; 6         int left = closestValue(root -> left, target); 7         int right = closestValue(root -> right, target); 8         double td = abs(root -> val - target), ld = abs(left - target), rd = abs(right - target); 9         if (td < ld) return td < rd ? root -> val : right;10         else return ld < rd ? left : right;11     }12 };

Notice that in the above code the properties of BST have not been used. So, what do you think? Well, the above code can be extended to Closest Binary Tree Value if this problem is published in the future :-) Well, Stefan posts several solutions (including a shorter C++ one) in 4 languages . So, refer to them and get more fun :-)

转载于:https://www.cnblogs.com/jcliBlogger/p/4763200.html

你可能感兴趣的文章