272. Closest Binary Search Tree Value II

NusterCache 發(fā)布于2019-08-14 17:35 / 3186人閱讀

摘要：題目鏈接的值大小順序?qū)嶋H上就是滿足的條件，所以直接中序遍歷，過程中維護一個，放入個當前離最近的值，的時，新的值和的距離如果小于隊首的那個值和的距離那么移除隊首，如果，且新的距離大于等于隊首的距離，直接退出，返回隊列中的所有結(jié)果。

272. Closest Binary Search Tree Value II

題目鏈接：https://leetcode.com/problems...

bst的值大小順序?qū)嶋H上就是滿足inorder的條件，所以直接中序遍歷，過程中維護一個queue，放入k個當前離target最近的值，queue的size=k時，新的值和target的距離如果小于隊首的那個值和target的距離那么移除隊首，如果size=k，且新的距離大于等于隊首的距離，直接退出，返回隊列中的所有結(jié)果。

/**
 * 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)的時間復(fù)雜度。提示找pre和suc，那么分別找到離k最近的pre和suc就好了，bst里面找離最近的k的復(fù)雜度是O(h),這個過程中要把路上的node存下來，以便找pre和next。
參考discussion里的：
https://discuss.leetcode.com/...