Clean Java O(<=n)solution using inOrder traverse. ~5ms


  • 0
    //LinkedList + inOrder traverse
    //When we are handling BST, inOrder traverse give us result ascendantly. This is the trick.
    //So we just pay attention to one situation below:
    //when we have k candidates (namely result is size of K),
    //if the leftmost element is too smaller than target comparing to the current node, we discard leftmost element and add the current value.
    //else we can return right away
        public List<Integer> closestKValues(TreeNode root, double target, int k) {
    	List<Integer> result = new LinkedList<Integer>();
            Stack<TreeNode> Tree = new Stack<TreeNode>();
            while(!Tree.isEmpty()||root!=null){
        	    if(root!=null){
        		Tree.push(root);
        		root = root.leftChild;
        	    }
        	    else{
        		root = Tree.pop();
        		if(result.size()==k){//special case: when we have k candidates
        		    if(Math.abs(result.get(0)-target) > Math.abs(root.val-target))
        		        {result.remove(0);result.add(root.val);}
        		    else break; // No need to traverse
        		}
        		else result.add(root.val); //normal case: we just do inOrder traverse
        		root = root.rightChild;      		
        	    }
            }
            return result;
        }

  • 0
    H

    @tongzhou2
    Your idea is a wonder. What a breathtaking solution!


Log in to reply
 

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