[c++] 5ms version: one queue and without reverse operation by using size of each level


  • 71
    S

    Assuming after traversing the 1st level, nodes in queue are {9, 20, 8}, And we are going to traverse 2nd level, which is even line and should print value from right to left [8, 20, 9].

    We know there are 3 nodes in current queue, so the vector for this level in final result should be of size 3.
    Then, queue [i] -> goes to -> vector[queue.size() - 1 - i]
    i.e. the ith node in current queue should be placed in (queue.size() - 1 - i) position in vector for that line.

    For example, for node(9), it's index in queue is 0, so its index in vector should be (3-1-0) = 2.

    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        if (root == NULL) {
            return vector<vector<int> > ();
        }
        vector<vector<int> > result;
    
        queue<TreeNode*> nodesQueue;
        nodesQueue.push(root);
        bool leftToRight = true;
    
        while ( !nodesQueue.empty()) {
            int size = nodesQueue.size();
            vector<int> row(size);
            for (int i = 0; i < size; i++) {
                TreeNode* node = nodesQueue.front();
                nodesQueue.pop();
    
                // find position to fill node's value
                int index = (leftToRight) ? i : (size - 1 - i);
    
                row[index] = node->val;
                if (node->left) {
                    nodesQueue.push(node->left);
                }
                if (node->right) {
                    nodesQueue.push(node->right);
                }
            }
            // after this level
            leftToRight = !leftToRight;
            result.push_back(row);
        }
        return result;
    }

  • 8
    Q

    I think use deque maybe more intuitive, no reverse too.

    for zig, popback, pushfront, left then right,

    for zag, popfront, pushback, right then left

    [clear iterative solution with deque, no reverse][1]
    [1]: https://leetcode.com/discuss/50994/clear-iterative-solution-with-deque-no-reverse


  • 0
    R

    deque is a pain to use


  • 0
    Q

    how it hurt? performance? or?


  • 0
    R

    I think it is hard to write the code without errors when using deque


  • 1
    T

    I thought deque is intuitive, but not really such helpful. Still need judge reverse or not, right? Is any better way to use deque? ....

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        deque<TreeNode*> doubleEndQueue;
        if(root)  doubleEndQueue.push_back(root);
        bool reverse = false;
        vector<vector<int>> zigzagResult;
        while(!doubleEndQueue.empty()){
            int size = doubleEndQueue.size();
            zigzagResult.push_back(vector<int>());
            for(int i=0; i<size; i++){
                if(!reverse){
                    auto node = doubleEndQueue.front();
                    zigzagResult.back().push_back(node->val);
                    doubleEndQueue.pop_front();
                    if(node->left)  doubleEndQueue.push_back(node->left);
                    if(node->right)  doubleEndQueue.push_back(node->right);
                }
                else{
                    auto node = doubleEndQueue.back();
                    zigzagResult.back().push_back(node->val);
                    doubleEndQueue.pop_back();
                    if(node->right)  doubleEndQueue.push_front(node->right);
                    if(node->left)  doubleEndQueue.push_front(node->left);                   
                }
    
            }
            reverse = !reverse;
        }
        return zigzagResult;
    }
    

    If only queue, with hint from StevenCooks, code is shorter.

     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        if(root)  q.push(root);
        bool reverse = false;
        vector<vector<int>> zigzagResult;
        while(!q.empty()){
            int size = q.size();
            zigzagResult.push_back(vector<int>(size));
            for(int i=0; i<size; i++){
                int index = (reverse) ? size-i-1 : i;
                zigzagResult.back()[index] = q.front()->val;
                if(q.front()->left)  q.push(q.front()->left);
                if(q.front()->right)  q.push(q.front()->right);
                q.pop();
            }
            reverse = !reverse;
        }
        return zigzagResult;
    }

  • 0
    Y

    your idea is beautiful. I like the symmetry in your idea. left<-->right switched, deque front<---> back switched.


  • 0

    Thanks so much for your code. I had a similar idea but I lost it when I was coding. Lol


  • 0

    Java solution

     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            if(root == null){
                return ret;
            }
            Queue<TreeNode> que = new LinkedList<>();
            que.offer(root);
            boolean flag = true;
            while(!que.isEmpty()){
                ArrayList<Integer> levelnode = new ArrayList<>();
                int len  = que.size();
                for(int i = 0; i < len; i++){
                    TreeNode temp = que.poll();
                    if(flag){
                        levelnode.add(temp.val);
                    }else{
                        levelnode.add(0,temp.val);
                    }
                    if(temp.left != null) que.offer(temp.left);
                    if(temp.right != null) que.offer(temp.right);
                }
                flag = !flag;
                ret.add(levelnode);
            }
            return ret;
        }
    

  • 0
    N

    @joy_zhou : I think this solution is terrible.


  • 0

    said in [c++] 5ms version: one queue and without reverse operation by using size of each level:

    ? i : (size - 1 - i);

    Really like you idea of obtaining the insertion index.


  • 0

    My python version.

    from collections import deque
    class Solution(object):
        def zigzagLevelOrder(self, root):
            if not root: return []
            queue = deque()
            queue.appendleft(root)
            res = []
            l2r = True
            while queue:
                size = len(queue)
                tmp = [0]*size
                for i in range(size):
                    node = queue.pop()
                    index = i if l2r else size-i-1
                    tmp[index] = node.val
                    map(lambda x: queue.appendleft(x), [x for x in [node.left, node.right] if x])
                res.append(tmp)
                l2r = not l2r
            return res
    

  • 0
    L
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> allres;
            queue<TreeNode*> q;
            
            if(root==nullptr) 
                return allres;
            
            bool isInOrder=true;
            q.push(root);
            
            while(!q.empty()) {
                vector<int> res;
                    
                if(isInOrder) {
                    int start=0,end=q.size();
                    while(start<end) {
                        TreeNode* current=q.front();
                        q.pop();
                        res.push_back(current->val);
                        if(current->right!=nullptr)
                            q.push(current->right);
                        if(current->left!=nullptr)
                            q.push(current->left);
                       // allres.push_back(res);
                        start++;
                        
                    }
                    
                    allres.push_back(res);
                    isInOrder=!isInOrder;
                }
                
                else {
                    int start=0,end=q.size();
                    while(start<end) {
                        TreeNode* current=q.front();
                        q.pop();
                        
                        res.push_back(current->val);
        
                        if(current->left!=nullptr)
                            q.push(current->left);
                        if(current->right!=nullptr)
                            q.push(current->right);
                   
                        start++;
                    }
                    allres.push_back(res);           
                    isInOrder=!isInOrder;
                }
                
            }
            
            
            return allres;
            
        }
    

    testcae: [1,2,3,4,null,null,5]
    true: [[1],[3,2],[4,5]]
    wrong:[[1],[3,2],[5,4]]

    why is the result wrong ?who can know the wrong position??


Log in to reply
 

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