前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode solution 270: Closest Binary Search Tree Value

Leetcode solution 270: Closest Binary Search Tree Value

作者头像
包子面试培训
发布2019-05-13 16:12:58
5780
发布2019-05-13 16:12:58
举报
文章被收录于专栏:包子铺里聊IT

WE ARE HIRING! Software engineer interviewers from Amazon, Facebook and Twitter. Please email baozitraining@outlook.com if you are interested

New leetcode solution video on YouTube.com/baozitraining

Leetcode solution 270: Closest Binary Search Tree Value

https://blog.baozitraining.org/2019/04/leetcode-solution-270-closest-binary.html

https://youtu.be/GcrvRcEM9Hs

Problem Statement

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:

代码语言:javascript
复制
Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

This is a very easy problem as long as you are familiar with Binary Search Tree. In order to find the value that is closest to the given target, we can traverse the tree and keep a record of the minimum delta. Of course we can traverse the entire tree but we can definite do it better by always branch out either left or right given the target and root node value. For example, if current node is 10, and target is 9, the next possible smaller value must exist only on the left part of or with the current node

代码语言:javascript
复制
     10
   /   \
  7     11

Solutions

Recursion solution

private double curMinDelta = Double.MAX_VALUE;

private int smallestValue = 0;

public int closestValue(TreeNode root, double target) {

this.searchMin(root, target);

return this.smallestValue;

}

private void searchMin(TreeNode root, double target) {

if (root == null) {

return;

}

if (target == root.val) {

this.smallestValue = root.val;

return;

}

double delta = Math.abs(target - root.val);

if (delta < this.curMinDelta) {

smallestValue = root.val;

this.curMinDelta = delta;

}

if (target < root.val) {

this.searchMin(root.left, target);

} else {

this.searchMin(root.right, target);

}

}

view rawCloestBinarySearchTreeValue.java hosted with ❤ by GitHub

Time Complexity: assuming tree size is N,O(lgN) since we are doing binary search Space Complexity:O(1) if not considering recursion function stacks.

Iterative solution
代码语言:javascript
复制
public int closestValue(TreeNode root, double target) {
    int ret = root.val;   
    while(root != null){
        if(Math.abs(target - root.val) < Math.abs(target - ret)){
            ret = root.val;
        }      
        root = root.val > target? root.left: root.right;
    }     
    return ret;
}
From: https://leetcode.com/problems/closest-binary-search-tree-value/discuss/70331/Clean-and-concise-java-solution

Time Complexity: assuming tree size is N,O(lgN) since we are doing binary search Space Complexity:O(1)

References
  • Leetcode discussion solution
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-04-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 包子铺里聊IT 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Problem Statement
  • Video Tutorial
  • Thought Process
  • Solutions
    • Recursion solution
      • Iterative solution
        • From: https://leetcode.com/problems/closest-binary-search-tree-value/discuss/70331/Clean-and-concise-java-solution
          • References
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档