Question

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

Solution

  • Method 1: recursion O(nlogn) ```Java /**
    • Definition for a binary tree node.
    • public class TreeNode {
    • int val;
    • TreeNode left;
    • TreeNode right;
    • TreeNode(int x) { val = x; }
    • } */ class Solution { private double diff = Double.MAX_VALUE; private int res; public int closestValue(TreeNode root, double target) { dfs(root, target); return this.res; } private void dfs(TreeNode node, double target){ if(node == null) return; else{ double diff = Math.abs(node.val - target); if(diff < this.diff){ this.diff = diff; this.res = node.val; } dfs(target < node.val ? node.left: node.right, target); } } } ```
  • Method 2: Itegeration 
      class Solution {
      public int maxSubArrayLen(int[] nums, int k) {
          Map<Integer, Integer> map = new HashMap<>();
          for(int i = 1; i < nums.length; i++){
              nums[i] += nums[i - 1];
          }
          int max = 0;
          map.put(0, -1);
          for(int i = 0; i < nums.length; i++){
              if(map.containsKey(nums[i] - k)){
                  max = Math.max(max, i - map.get(nums[i] - k));
              }
              if(!map.containsKey(nums[i])){
                  map.put(nums[i], i);
              }
          }
          return max;
      }
  }