Java in-order traversal 1ms solution


  • 28
    M
    public class Solution {
        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            LinkedList<Integer> list = new LinkedList<Integer>();
            closestKValuesHelper(list, root, target, k);
            return list;
        }
        
        /**
         * @return <code>true</code> if result is already found.
         */
        private boolean closestKValuesHelper(LinkedList<Integer> list, TreeNode root, double target, int k) {
            if (root == null) {
                return false;
            }
            
            if (closestKValuesHelper(list, root.left, target, k)) {
                return true;
            }
            
            if (list.size() == k) {
                if (Math.abs(list.getFirst() - target) < Math.abs(root.val - target)) {
                    return true;
                } else {
                    list.removeFirst();
                }
            }
            
            list.addLast(root.val);
            return closestKValuesHelper(list, root.right, target, k);
        }
    }

  • 0
    Y

    Your intuition is to go to the leftmost, and then remove nodes that are too small from the front of the list, is it correct?

    Time complexity O(n), space complexity O(k), and running time is 1ms. Seems so much faster than my 5ms solution which is O(klogn) in both time and space. Why is it like that?

    My solution is here: https://leetcode.com/discuss/71820/java-5ms-iterative-following-hint-o-klogn-time-and-space


  • 0
    Y

    @yanggao, I have the same question as you did. I am also wondering why this O(N) solution is faster than O(klogn) solution..

    One possible guess is that when k is a large value, say is n/2, than O(klogN) is acutally O(NlogN), which is slower than O(N)...


  • 0
    Y

    hi @zjuzhanxf, agree with you that big k may be one cause, since when k == 1, the O(logn) solution should be much faster than the O(n) solution...

    other causes I can think of:

    1. space consumption. The O(n) solution has space complexity as O(k), and ours is O(klogn). allocating space takes time.

    2. overhead from stack operations.

    3. the target in the test cases may be close to the left end.

    What a shame that we cannot see the test cases...


  • 1
    M

    Here is my iterative code, 4ms; I cannot get 1ms, maybe more testing cases are added?

        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            LinkedList<Integer> result = new LinkedList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode cur=root; 
            
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            
            while( stack.size()>0 ){
                cur=stack.pop();
                if( result.size()==k )
                    if( Math.abs( result.getFirst() - target ) <= Math.abs( cur.val - target ) )
                        break; //find all K values
                    else
                        result.removeFirst();
                
                result.add(cur.val);
                cur=cur.right;
                while(cur!=null){
                    stack.push(cur);
                    cur=cur.left;
                }
            }
            return result; 
        }
    

  • 1

    a little optimization for the iterate one.

        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            LinkedList<Integer> ans = new LinkedList();
            Stack<TreeNode> stack = new Stack<>();
            while (root != null || !stack.isEmpty()) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (ans.size() == k) {
                    if (Math.abs(root.val - target) > Math.abs(ans.get(0) - target)) {
                        break;
                    } else {
                        ans.pollFirst();
                    }
                }
                ans.offer(root.val);
                root = root.right;
            }
            return ans;
        }
    

  • 0

    CPP version:

    vector<int> closestKValues(TreeNode* root, double target, int k) 
    {
    	deque<int> dq;
    	stack<TreeNode*> st;
    	while (root || !st.empty())
    	{
    		if (root)
    		{
    			st.push(root);
    			root = root->left;
    		}
    		else
    		{
    			root = st.top();
    			st.pop();
    			if (dq.size() == k && abs(dq.front() - target) >= abs(root->val - target))
    				dq.pop_front();
    			if (dq.size() < k)
    				dq.push_back(root->val);
    			root = root->right;
    		}
    	}
    	return vector<int>(dq.begin(), dq.end());
    }
    

  • 0
    Y
    This post is deleted!

  • 0
    Y
    This post is deleted!

Log in to reply
 

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