/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
char closest(TreeNode * root, double target){
TreeNode* left = root->left;
TreeNode* right = root->right;
// a helper function, return who is the cloest to the target among root, left, and right
if (left == nullptr){
if (right == nullptr) return 't';
else{
// if left == null and right != null: decide return root or right
if (abs(root->val - target) < abs(right->val - target)) return 't';
else return 'r';
}
}
else {
if (right == nullptr){
// left != nullptr but right == nullptr
if (abs(root->val - target) < abs(left->val - target)) return 't';
else return 'l';
}
else {
// left != nullptr, right != nullptr
if (abs(root->val - target) < abs(left->val - target) && abs(root->val - target) < abs(right->val - target))
return 't';
else if (abs(left->val - target) < abs(root->val - target) && abs(left->val - target) < abs(right->val - target))
return 'l';
else if (abs(right->val - target) < abs(root->val - target) && abs(right->val - target) < abs(left->val - target))
return 'r';
}
}
}
int closestValue(TreeNode* root, double target) {
// recursive
switch(closest(root, target)){
case 't':
return root->val;
break;
case 'r':
return closestValue(root->right, target);
break;
case 'l':
return closestValue(root->left, target);
break;
}
}
};
1 Response
Write a comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.