[Leetcode] Closest Binary Search Tree Value 最近二叉搜索

AlphaWallet 发布于2019-08-14 12:37 / 2877人阅读

摘要：递归法复杂度时间空间思路根据二叉树的性质，我们知道当遍历到某个根节点时，最近的那个节点要么是在子树里面，要么就是根节点本身。因为我们知道离目标数最接近的数肯定在二叉搜索的路径上。

Closest Binary Search Tree Value I

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.

递归法 复杂度

时间 O(logN) 空间 O(H)

思路

根据二叉树的性质，我们知道当遍历到某个根节点时，最近的那个节点要么是在子树里面，要么就是根节点本身。所以我们根据这个递归，返回子树中最近的节点，和根节点中更近的那个就行了。

代码

public class Solution {
    public int closestValue(TreeNode root, double target) {
        // 选出子树的根节点
        TreeNode kid = target < root.val ? root.left : root.right;
        // 如果没有子树，也就是递归到底时，直接返回当前节点值
        if(kid == null) return root.val;
        // 找出子树中最近的那个节点
        int closest = closestValue(kid, target);
        // 返回根节点和子树最近节点中，更近的那个节点
        return Math.abs(root.val - target) < Math.abs(closest - target) ? root.val : closest;
    }
}

迭代法 复杂度

时间 O(logN) 空间 O(H)

思路

记录一个最近的值，然后沿着二叉搜索的路径一路比较下去，并更新这个最近值就行了。因为我们知道离目标数最接近的数肯定在二叉搜索的路径上。

代码

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        while(root != null){
            // 如果该节点的离目标更近，则更新到目前为止的最近值
            closest = Math.abs(closest - target) < Math.abs(root.val - target) ? closest : root.val;
            // 二叉搜索
            root = target < root.val ? root.left : root.right;
        }
        return closest;
    }
}

Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note: Given target value is a floating point. You may assume k is always valid, that is: k ≤ total nodes. You are guaranteed to have only one unique set of k values in the BST that are closest to the target. Follow up: Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

Consider implement these two helper functions: getPredecessor(N), which returns the next smaller node to N. getSuccessor(N), which returns the next larger node to N.

中序遍历法 复杂度

时间 O(N) 空间 Max(O(K),O(H))

思路

二叉搜索树的中序遍历就是顺序输出二叉搜索树，所以我们只要中序遍历二叉搜索树，同时维护一个大小为K的队列，前K个数直接加入队列，之后每来一个新的数（较大的数），如果该数和目标的差，相比于队头的数离目标的差来说，更小，则将队头拿出来，将新数加入队列。如果该数的差更大，则直接退出并返回这个队列，因为后面的数更大，差值也只会更大。

代码

public class Solution {
    public List closestKValues(TreeNode root, double target, int k) {
        Queue klist = new LinkedList();
        Stack stk = new Stack();
        // 迭代中序遍历二叉搜索树的代码
        while(root != null){
            stk.push(root);
            root = root.left;
        }
        while(!stk.isEmpty()){
            TreeNode curr = stk.pop();
            // 维护一个大小为k的队列
            // 队列不到k时直接加入
            if(klist.size() < k){
                klist.offer(curr.val);
            } else {
            // 队列到k时，判断下新的数是否更近，更近就加入队列并去掉队头
                int first = klist.peek();
                if(Math.abs(first - target) > Math.abs(curr.val - target)){
                    klist.poll();
                    klist.offer(curr.val);
                } else {
                // 如果不是更近则直接退出，后面的数只会更大
                    break;
                }
            }
            // 中序遍历的代码
            if(curr.right != null){
                curr = curr.right;
                while(curr != null){
                    stk.push(curr);
                    curr = curr.left;
                }
            }
        }
        // 强制转换成List，是用LinkedList实现的所以可以转换
        return (List)klist;
    }
}

GPU云服务器云服务器 binary-search-tree binary-tree binary-search closest()

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64600.html

LeetCode 272 Closest Binary Tree Traversal II 解题思路

摘要：原题网址题意在二叉搜索树当中找到离最近的个数。解题思路由于二叉搜索数的中序遍历是有序的，比如例子中的树，中序遍历为。原题网址：https://leetcode.com/problems... Given a non-empty binary search tree and a target value, find k values in the BST that are closes...

Youngdze 2019-08-16 13:26 评论0 收藏0
LeetCode[270] Closest Binary Search Tree Value

摘要：复杂度思路用一个变量来记录当前的值，并且在每次之前，比较得到目前的最大值。注意变量的比较不要用代码 LeetCode[270] Closest Binary Search Tree Value Given a non-empty binary search tree and a target value, find the value in the BST that is close...

pumpkin9 2019-08-14 15:02 评论0 收藏0
[LeetCode] 270. Closest Binary Search Tree Value

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...

XUI 2019-08-16 13:49 评论0 收藏0
272. Closest Binary Search Tree Value II

摘要：题目链接的值大小顺序实际上就是满足的条件，所以直接中序遍历，过程中维护一个，放入个当前离最近的值，的时，新的值和的距离如果小于队首的那个值和的距离那么移除队首，如果，且新的距离大于等于队首的距离，直接退出，返回队列中的所有结果。 272. Closest Binary Search Tree Value II 题目链接：https://leetcode.com/problems... ...

NusterCache 2019-08-14 17:35 评论0 收藏0
LeetCode 之 JavaScript 解答第98题 —— 验证二叉搜索树

摘要：小鹿题目验证二叉搜索树给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。算法思路定义全局的变量，用来返回是否为二叉搜索树。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

用户84 2019-08-23 17:12 评论0 收藏0