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.
Example:
Input: root = [4,2,5,1,3], target = 3.714286 4 / \ 2 5 / \ 1 3 Output: 4
A:
就是对比呗。没啥特别的地方
/** * 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) { if(target < root->val){ if(root->left){ int left = closestValue(root->left, target); if(abs(left - target) < abs(target - root->val)) return left; } } if(target > root->val){ if(root->right){ int right = closestValue(root->right, target); if(abs(right - target) < abs(target - root->val)) return right; } } return root->val; } };
No comments:
Post a Comment