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


  • 73
    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??


  • 0
    A

    it is truly a good way to solve this problem


  • 0
    F

    Same idea, use BFS, written in java

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            Queue<TreeNode> que = new LinkedList<>();
            int flag = 1;
            que.add(root);
            
            while (!que.isEmpty()) {
                int size = que.size();
                ArrayList<Integer> tmp = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode curr = que.poll();
                    tmp.add(curr.val);
                    
                    if (curr.left != null) {
                        que.add(curr.left);
                    }
                    if (curr.right != null) {
                        que.add(curr.right);
                    }
                }
                if (flag == 1) {
                    res.add(tmp);
                } else if (flag == 0) {
                    Collections.reverse(tmp);
                    res.add(tmp);
                }
                
                flag = (flag + 1) % 2;
            }
            return res;
        }
    }
    
    

  • 0
    D

    I guess use list we can have better performance than deque, am I right?


Log in to reply
 

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