摘要:复杂度思路用一个变量来记录当前的值,并且在每次之前,比较得到目前的最大值。注意变量的比较不要用代码
LeetCode[270] Closest Binary Search Tree Value
RecursionGiven 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.
复杂度
O(N), O(lgN)
思路
用一个变量来记录当前的值,并且在每次recursion之前,比较得到目前的最大值。注意double变量的比较不要用==
代码
double min = Double.MAX_VALUE; int val = 0; public int closetValue(TreeNode root, double target) { helper(root, target); return val; } public void helper(TreeNode root, double target) { if(root == null) return; if(Math.abs(target - root.val) < min) { min = Math.abs(target - root.val); val = root.val; } if(root.val > target) { helper(root.left, target); } else { helper(root.right, target); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65253.html
Problem 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 o...
摘要:递归法复杂度时间空间思路根据二叉树的性质,我们知道当遍历到某个根节点时,最近的那个节点要么是在子树里面,要么就是根节点本身。因为我们知道离目标数最接近的数肯定在二叉搜索的路径上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...
摘要:题目链接的值大小顺序实际上就是满足的条件,所以直接中序遍历,过程中维护一个,放入个当前离最近的值,的时,新的值和的距离如果小于队首的那个值和的距离那么移除队首,如果,且新的距离大于等于队首的距离,直接退出,返回队列中的所有结果。 272. Closest Binary Search Tree Value II 题目链接:https://leetcode.com/problems... ...
摘要:原题网址题意在二叉搜索树当中找到离最近的个数。解题思路由于二叉搜索数的中序遍历是有序的,比如例子中的树,中序遍历为。 原题网址:https://leetcode.com/problems... Given a non-empty binary search tree and a target value, find k values in the BST that are closes...
摘要:解题思路对于二叉搜索树,我们很容易会想到使用栈和队列来解决问题,本题是要求实现一个对二叉搜索树的遍历器,要求每次可以返回最小的节点值,我们使用栈。 Binary Search Tree IteratorImplement an iterator over a binary search tree (BST). Your iterator will be initialized with...
阅读 2478·2023-04-25 21:26
阅读 1486·2021-11-25 09:43
阅读 1899·2019-08-30 15:52
阅读 914·2019-08-30 14:05
阅读 2598·2019-08-29 16:10
阅读 395·2019-08-29 13:48
阅读 1837·2019-08-29 12:47
阅读 1257·2019-08-23 18:04