leetcode270. 最接近的二叉搜索树值

给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的数值。

注意：

给定的目标值 target 是一个浮点数
题目保证在该二叉搜索树中只会存在一个最接近目标值的数
示例：

输入: root = [4,2,5,1,3]，目标值 target = 3.714286

    4
   / \
  2   5
 / \
1   3

输出: 4

思路：二分，当前节点比target大就往左边搜（因为右边的差距更大），当前节点比target小就往右搜（因为左边的差距更大）。

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for a binary tree node.
     
    
   

    

     

    
    

     

       * public class TreeNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * TreeNode left;
     
    
   

    

     

    
    

     

       * TreeNode right;
     
    
   

    

     

    
    

     

       * TreeNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
  public int closestValue(TreeNode root, double target) {
     
    
   

    

     

    
    

     
 int val, closest = root.val;
     
    
   

    

     

    
    

     
 while (root != null) {
     
    
   

    

     

    
    

     

       val = root.val;
     
    
   

    

     

    
    

     

       closest = Math.abs(val - target) < Math.abs(closest - target) ? val : closest;
     
    
   

    

     

    
    

     

       root =  target < root.val ? root.left : root.right;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return closest;
     
    
   

    

     

    
    

     

        }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104144811