Inorder One LinkedList Java solution beat 85%


  • 10

    This solution is maintaining a linkedlist and break the travelsal when the rightmost is larger than the leftmost.

    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new LinkedList<Integer>();
        helper(root, target, k, res);
        return res;
    }
    private void helper(TreeNode root, double target, int k, List<Integer> res) {
        if (root == null) {
            return;
        }
        helper(root.left,target,k,res);
        if (res.size()< k) {
            res.add(root.val);
        } else {
            if (Math.abs(res.get(0)-target) > Math.abs(root.val-target)) {
                res.remove(0);
                res.add(root.val);
            } else {
                return;
            }
        }
        helper(root.right,target,k,res);
    }

  • 0
    I

    Why are you adding current node to list if it is closer than the first node? Why compare with first node?


  • 0
    T

    can remove

    else {
                return;
            }
    

  • 0
    I

    @tinalxj12 No, this can't be removed. This is the tricky part of pruning, which means you can avoid traversing right child. I got similar idea.

    Queue<Integer> q = new LinkedList<>();
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        helper(root, target, k);
        List<Integer> res = new ArrayList<>(q);
        return res;
    }
    
    public void helper(TreeNode node, double target, int k) {
        if (node == null) {
            return;
        }
        helper(node.left, target, k);
        handle(node, target, k);
    }
    
    public void handle(TreeNode node, double target, int k) {
        if (q.size() < k) {
            q.offer(node.val);
            helper(node.right, target, k);
        } else {
            double v1 = Math.abs(node.val - target);
            double v2 = Math.abs(q.peek() - target);
            if (v1 < v2) {
                q.poll();
                q.offer(node.val);
                helper(node.right, target, k);
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.