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>();
        		root = root.leftChild;
        		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))
        		    else break; // No need to traverse
        		else result.add(root.val); //normal case: we just do inOrder traverse
        		root = root.rightChild;      		
            return result;

  • 0

    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.