Accepted C++ Non-recursion Solution with One Queue and One Loop


  • 2
    C
    class Solution {
    public:
        vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
            vector<vector<int>> ret;
            if(root == NULL) return ret;
            vector<int> level;
            bool tag = true;    //define the order of output(left to right or right to left)
            
            queue<TreeNode*> TreeQ;
            TreeQ.push(root);
            TreeQ.push(NULL);   //distinguish one level from another level
            
            while(!TreeQ.empty())
            {
                TreeNode* node = TreeQ.front();
                TreeQ.pop();
                if(node != NULL)
                {
                    level.push_back(node->val);
                    if(node->left) TreeQ.push(node->left);
                    if(node->right) TreeQ.push(node->right);
                }
                else
                {
                    if(tag)
                    {
                        ret.push_back(level);
                    }
                    else
                    {
                        reverse(level.begin(), level.end());
                        ret.push_back(level);
                    }
                    tag = !tag;
                    if(!TreeQ.empty())   // avoid endless loop to last level of tree
                    {
                        level.clear();
                        TreeQ.push(NULL);
                    }
                }
            }
            
            return ret;
        }
    };
    

    I used two tricks:

    1. Insert "NULL" to distinguish one level from another level

    2. used one tag to define the order of output , meaning from left to right or right to left.


  • 0
    D

    In term of clarity, do you think if using 2 list is better than 1 list? if it is, below is the java solution:

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            boolean fromLeft = true;
            
            List<List<Integer>> results = new ArrayList<List<Integer>>();
            if(root == null) return results;
            
            ArrayList<TreeNode> l1 = new ArrayList<TreeNode>();
            ArrayList<TreeNode> l2;
            l1.add(root);
            
            while(!l1.isEmpty()){
                int z = l1.size();
                l2 = new ArrayList<TreeNode>();
                List<Integer> r = new ArrayList<Integer>();
                TreeNode n;
                for(int i=0; i<z; i++){
                    n = l1.get(i);
                    if(n.left!=null) l2.add(n.left);
                    if(n.right!=null) l2.add(n.right);
                    if(fromLeft){
                        r.add(l1.get(i).val);
                    }else {
                        r.add(l1.get(z-1-i).val);
                    }
                }
                results.add(r);
                fromLeft = !fromLeft;
                l1 = l2;
            }
            
            return results;
        }
    }

Log in to reply
 

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