Another solution without stack. Pretty Simple (4ms)


  • 0
    M

    The idea is simple. Run an inorder traversal, delete larger node difference between the first node and the last node until we reach size k. One thing worthy of noticing is that I use remove operation of list and this costs O(n). If we replace list with deque, it might run faster, but this will require two pass(passing deque value to list).

        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            List<Integer> result=new ArrayList<Integer>();
    
            inorder(result,root);
            while(result.size()>k){
                double d1=Math.abs(result.get(0)-target);
                double d2=Math.abs(result.get(result.size()-1)-target);
                if(d1>d2) result.remove(0);
                else result.remove(result.size()-1);
            }
            return result;
        }
        public void inorder(List<Integer> result,TreeNode root){
            if(root.left!=null) inorder(result,root.left);
            result.add(root.val);
            if(root.right!=null) inorder(result,root.right);
        }
    

Log in to reply
 

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