Timeout ?? using 2 queues but O(N) only..... Need urgent help....Thanks..


  • 0
    M

    Why Timeout is occurring.... it O(N) only...Anyone knows how to do it using 1 queue only ?

    vector<vector<int> > levelOrder(TreeNode *root) 
            {
                vector<vector<int> >v;
                vector<int> level;
                queue<TreeNode *> parent, curr, empty;
        
                if(!root)
                    return v;
                curr.push(root);
        
                while(!curr.empty())
                {
                    swap(parent, curr);
                    swap(curr, empty);
                    
                    while(!parent.empty())
                    {
                        TreeNode * temp = parent.front();
                        parent.pop();
            
                        level.push_back(temp->val);
                        if(temp->left!=NULL)
                            curr.push(temp->left);
                        if(temp->right !=NULL)
                            curr.push(temp->right);
                    }
                    v.push_back(level);
                    
                }
        
                return v;
                
            }

  • 0
    M

    As the main difference between your algorithm and mine is based on the multiple queues and swapping between them, I would assume that it is because of the swap method. Since the variables for the queues are local, you must be moving the values in each queue from one to the other, which will take quite a bit of time.

    I did this in Java, but the underlying principle is the same. You are only using one queue at a time, so storing an element that means "switch queues" would allow you to ignore the inner while condition. If you have the "switch" element, push level onto the result queue, then start work of the next level. As the "switch" element is part of the queue, you can add the children to the end, and they'll be after the switch.

    As everything is in one queue, the swap method won't be needed, cutting down the time required to run it.


  • 4
    S
    class Solution {
    public:
        void levelOrder_helper(TreeNode* root, int level, vector<vector<int>>& result){
            if(!root) return;
            if(result.size() <= level){
                vector<int> tmp;
                result.push_back(tmp);
            }
            result[level].push_back(root->val);
            levelOrder_helper(root->left, level+1, result);
            levelOrder_helper(root->right, level+1, result);
        }
        
        vector<vector<int> > levelOrder(TreeNode *root) {
            vector<vector<int>> result;
            levelOrder_helper(root, 0, result);
            return result;
        }
    };
    

    Using BFS is definitely a good approach, but it is hard to find the "break point" for each level. I used recursion and pass the level down as an argument. And pass the result vector as reference at the main time. Therefore I dont need to keep track of parent nodes and try to find the "break points" any more.


  • 5
    Y

    I used one queue. Just keep adding TreeNodes to the same queue. To tell different levels, I used a dummy node: every time we see the dummy node, we know it is the end of the level. Then, we insert another dummy node to the queue to mark the end of the next level. I think a counter will also work ok.
    Following is my code: (I hope it helps)

        public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        TreeNode dummy = new TreeNode(1);
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null) return result;
        
        ArrayList<Integer> tmpal = new ArrayList<Integer>();
        q.add(root); q.add(dummy);
        while (!q.isEmpty()) {
            TreeNode tmp = q.poll();
            if (tmp == dummy) {
                q.add(dummy);
                if (tmpal.isEmpty()) break; //to avoid infinite loop
                result.add(tmpal);
                tmpal = new ArrayList<Integer>();
            }
            else {
                if (tmp.left != null) q.add(tmp.left); 
                if (tmp.right != null) q.add(tmp.right);
                tmpal.add(tmp.val);
            }
        }
        return result;
        
    }

  • 0
    M

    Did your code pass? You should fail for {1} case.


  • 0
    X

    if (tmp == dummy) {
    //not only their value equal but the hasCode equal, we can regard they are the same object


  • 1

    use one deque, with NULL as the level tag!

    class Solution {
    public:
        std::vector<std::vector<int> > levelOrder(TreeNode *root) {
            std::vector<std::vector<int> > result;
    		if (root == NULL)
    			return result;
    		std::deque<TreeNode *> wait_nodes;
    		wait_nodes.push_back(root);
    		wait_nodes.push_back(NULL);
    		std::vector<int> nodes_val;
    		while (wait_nodes.size() != 1) {
    			root = wait_nodes.front();
    			wait_nodes.pop_front();
    			while (root != NULL) {
    				nodes_val.push_back(root->val);
    				if (root->left != NULL)
    					wait_nodes.push_back(root->left);
    				if (root->right != NULL)
    					wait_nodes.push_back(root->right);
    				root = wait_nodes.front();
    				wait_nodes.pop_front();
    			}
    			result.push_back(nodes_val);
    			wait_nodes.push_back(NULL);
    			nodes_val.clear();
    		}
    		return result;
        }
    };

Log in to reply
 

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