270.Closest-Binary-Search-Tree-Value.md

270. Closest Binary Search Tree Value

---

题目地址

https://leetcode.com/problems/closest-binary-search-tree-value/

题目描述

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

代码

Approach #1 Recursive Inorder O(n)

/**
 * 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) {
		List<Integer> nums = new ArrayList();
    inorder(root, nums);
    return Collections.min(nums, new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return Math.abs(o1 - target) - Math.abs(o2 - target);
      }
    });
  }
  
  private void inorder(TreeNode root, List<Integer> nums) {
    if (root == null)	return;
    inorder(root.left, nums);
    nums.add(root.val);
    inorder(root.right, nums);
  }
}

Approach #2 Iterative Inorder

class Solution {
  public int closestValue(TreeNode root, double target) {
    LinkedList<TreeNode> stack = new LinkedList();
    long pred = Long.MIN_VALUE;
    
    while (!stack.isEmpty() || root != null) {
      while (root != null) {
        stack.add(root);
        root = root.left;
      }
      root = stack.removeLast();
      
      if (pred <= target && target < root.val) {
        return Math.abs(pred - target) ? (int)pred : root.val;
      }
      pred = root.val;
      
      root = root.right;
    }
    
    return (int)pred;
  }
}

Approach #3 Binary Search

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;
  }
}