Google+ Followers

Monday, August 7, 2017

[Leetcode] Closest Binary Search Tree Value, Solution

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.
[Thoughts]
遍历二叉搜索树,在遍历的过程中,对于遍历节点记录closest。


[Code]
1:    int closestValue(TreeNode* root, double target) {  
2:      double min = UINT_MAX;  
3:      int closeVal = 0;  
4:        
5:      closest(root, target, min, closeVal);  
6:      return closeVal;  
7:    }  
8:      
9:    void closest(TreeNode* root, double target, double& min, int& closeVal) {  
10:      if(root == NULL) return;  
11:        
12:      if(abs(target - root->val) < min) {  
13:        closeVal = root->val;  
14:        min = abs(target - root->val);  
15:      }  
16:        
17:      if(root->val < target) {  
18:        closest(root->right, target, min, closeVal);  
19:      }else {  
20:        closest(root->left, target, min, closeVal);  
21:      }  
22:    }  



Post a Comment