My accepted python code with one queue. Why do we need two stacks if one queue will do?


  • 2
    S

    Hello. Similar to someone's question here, I use one queue and do BFS. I maintain the level of the node along with it so I simply do in place reversal of the list of the traversed nodes. This just means calling

    if this_level > 0 and this_level%2==0: result[-1] = result[-1][::-1]
    

    in Python. I haven't read the two stack solution yet because I want to solve the problem myself. But I need to be convinced why such an approach is preferable over straightforward(probably this approach comes to mind for most people as well?) BFS solution.

    class Elem:
        def __init__(self, node, level):
            self.node  = node
            self.level = level
    
    class Solution:
        # @param root, a tree node
        # @return a list of lists of integers
        def zigzagLevelOrder(self, root):
            result = []
            if not root: return []
            
            q = collections.deque()
            q.appendleft(Elem(root, 0))
            
            prev_level = -1
            while q:
                elem = q.pop()
                this_node, this_level = elem.node, elem.level
                
                # record result
                if this_level != prev_level:
                    # reverse prev list if this_level is even
                    if this_level > 0 and this_level%2==0:
                        result[-1] = result[-1][::-1]
                    
                    result.append([this_node.val])
                    prev_level = this_level
                else:
                    result[-1].append(this_node.val)
                    
                # push the children to the queue
                if this_node.left != None:
                    q.appendleft(Elem(this_node.left, this_level+1))
                if this_node.right != None:
                    q.appendleft(Elem(this_node.right, this_level+1))
                    
            if this_level>0 and this_level%2==1:
                result[-1] = result[-1][::-1]
                
            return result

  • 0
    S

    I'm attaching C++ version of the above solution as well. The algorithm is the same as above. Just written in C++. The running time is 244ms (Python) vs 36ms (C++).

    class Elem {
    public:
        TreeNode* node;
        int level;
        Elem(TreeNode* _node, int _level){
            node = _node;
            level = _level;
        }
    }; 
     
    class Solution {
    public:
        vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
            vector<vector<int>> result;
            if (root==NULL) return result;
    
            queue<Elem> q;
            q.push(Elem(root, 0));
            
            int prev_level = -1, this_level = -1;
            
            while (q.size() > 0){
                Elem elem = q.front();
                TreeNode* this_node = elem.node;
                this_level = elem.level;
                q.pop();
                
                // push to the result.
                if (this_level != prev_level){
                    // reverse prev level result if cur level is even
                    if (this_level >0 && this_level%2==0) reverse(result.back().begin(), result.back().end());
                    prev_level = this_level;
                    result.push_back(vector<int>(1,this_node->val));
                } else {
                    result.back().push_back(this_node->val);
                }
                
                // push the children to the q
                if (this_node->left != NULL) q.push(Elem(this_node->left, this_level+1));
                if (this_node->right !=NULL) q.push(Elem(this_node->right, this_level+1));
            }
            
            if (this_level%2==1) reverse(result.back().begin(), result.back().end());
            return result;
        }
    };

  • 1
    H

    to make C++ solution more concise

        vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int>> res;
        if(!root)return res;
        
        queue<TreeNode *> q;
        q.push(root);
        int cur=1,next=0;
        bool flag=false;
        vector<int> tmp;
        while(!q.empty())
        {
            TreeNode *p=q.front();
            q.pop();
            tmp.push_back(p->val);
            cur--;
            if(p->left){q.push(p->left);next++;}
            if(p->right){q.push(p->right);next++;}
            if(cur==0)
            {
                if(flag)reverse(tmp.begin(),tmp.end());
                res.push_back(tmp);
                tmp.clear();
                cur=next;
                next=0;
                flag=!flag;
            }
        }
        
        return res;
    }

  • 0

    The reversal part will cause double time-overhead. Even your algorithm is also O(n), the time needed to perform traversal is twice as two-stack version.


Log in to reply
 

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