272. Closest Binary Search Tree Value II

NusterCache 发布于2019-08-14 17:35 / 3128人阅读

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

272. Closest Binary Search Tree Value II

题目链接：https://leetcode.com/problems...

bst的值大小顺序实际上就是满足inorder的条件，所以直接中序遍历，过程中维护一个queue，放入k个当前离target最近的值，queue的size=k时，新的值和target的距离如果小于队首的那个值和target的距离那么移除队首，如果size=k，且新的距离大于等于队首的距离，直接退出，返回队列中的所有结果。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List closestKValues(TreeNode root, double target, int k) {
        Queue q = new LinkedList();
        TreeNode prev = null, cur = root;
        while(cur != null) {
            if(cur.left == null) {
                if(q.size() == k) {
                    if(Math.abs(q.peek() - target) <= Math.abs(cur.val - target)) break;
                    q.poll();
                }
                q.offer(cur.val);
                cur = cur.right;
            }
            else {
                prev = cur.left;
                while(prev.right != cur && prev.right != null) prev = prev.right;
                // connect the prev with current
                if(prev.right == null) {
                    prev.right = cur;
                    cur = cur.left;
                }
                // traverse to current node
                else {
                    prev.right = null;
                    if(q.size() == k) {
                        if(Math.abs(q.peek() - target) <= Math.abs(cur.val - target)) break;
                        q.poll();
                    }
                    q.offer(cur.val);
                    cur = cur.right;
                }
                
            }
        }
        
        return (List) q;
    }
}

按要求是要O(h)的时间复杂度。提示找pre和suc，那么分别找到离k最近的pre和suc就好了，bst里面找离最近的k的复杂度是O(h),这个过程中要把路上的node存下来，以便找pre和next。
参考discussion里的：
https://discuss.leetcode.com/...

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/66678.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] Closest Binary Search Tree Value 最近二叉搜索

摘要：递归法复杂度时间空间思路根据二叉树的性质，我们知道当遍历到某个根节点时，最近的那个节点要么是在子树里面，要么就是根节点本身。因为我们知道离目标数最接近的数肯定在二叉搜索的路径上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...

AlphaWallet 2019-08-14 12:37 评论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
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0