My accepted JAVA solution


  • 105
    W
    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
        {
            List<List<Integer>> sol = new ArrayList<>();
            travel(root, sol, 0);
            return sol;
        }
        
        private void travel(TreeNode curr, List<List<Integer>> sol, int level)
        {
            if(curr == null) return;
            
            if(sol.size() <= level)
            {
                List<Integer> newLevel = new LinkedList<>();
                sol.add(newLevel);
            }
            
            List<Integer> collection  = sol.get(level);
            if(level % 2 == 0) collection.add(curr.val);
            else collection.add(0, curr.val);
            
            travel(curr.left, sol, level + 1);
            travel(curr.right, sol, level + 1);
        }
    }
    
    1. O(n) solution by using LinkedList along with ArrayList. So insertion in the inner list and outer list are both O(1),
    2. Using DFS and creating new lists when needed.

    should be quite straightforward. any better answer?


  • 0
    W
    This post is deleted!

  • 13
    M

    My iterative solution:

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rlts = new ArrayList<List<Integer>>();
        if (root == null) {
            return rlts;
        } 
        
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.add(root);
        boolean isForward = true;
        int lvlNumNodes = 1;
        LinkedList<Integer> rlt = new LinkedList<Integer>();
        
        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            
            // From left to right
            if (isForward) {
                rlt.add(node.val);
            } else {
                // From right to left
                rlt.addFirst(node.val);
            }
            
            if (node.left != null) {
                que.add(node.left);
            }
            
            if (node.right != null) {
                que.add(node.right);
            }
            
            --lvlNumNodes;
            // New level
            if (lvlNumNodes == 0) {
                rlts.add(rlt);
                lvlNumNodes = que.size();
                
                if (lvlNumNodes != 0) {
                    rlt = new LinkedList<Integer>();
                }
                
                // Change direction
                isForward = !isForward;
            }
        }
        
        return rlts;
    }

  • 0
    M

    I tried C++ version , but I got :

    10 / 33 test cases passed.
    

    Any help?

    void zigzag(TreeNode *root, list<list<int>> &res, int level) {
        if (root == nullptr) return;
        list<int> tmp;
        if (res.size() > level) {tmp = res.back();res.pop_back();}
        
        level%2 == 0 ? tmp.push_back(root->val) : tmp.push_front(root->val);
        res.push_back(tmp);
        
        zigzag(root->left,res,level+1);
        zigzag(root->right,res,level+1);
    }
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int>> res;
        list<list<int>> tmp;
        if (root == nullptr) return res;
        
        zigzag(root,tmp,0);
        for (auto lst : tmp) {
            vector<int> vec(lst.begin(),lst.end());
            res.push_back(vec);
        }
        return res;
    }

  • 0
    C

    Was solution accepted by OJ? Seems like lvlNumNodes needs to be decremented after que.poll();


  • 0
    M

    Yes, it's accepted. Actually, it has been decremented after each poll().


  • 0
    H

    See my answer is the C++ version.


  • 6
    H

    Thanks for sharing! Below is the 4ms C++ version.:

    class Solution {
    public:
        void travel(TreeNode* cur, vector<vector<int>> &res, int level) {
            if (cur == NULL)    return;
            
            if (res.size() <= level) {
                vector<int> newLevel;
                res.push_back(newLevel);
            }
            
            if (level % 2 == 0)
                res[level].push_back(cur->val);
            else
                res[level].insert(res[level].begin(), cur->val);
            
            travel(cur->left, res, level+1);
            travel(cur->right, res, level+1);
        }
    
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> res;
            travel(root, res, 0);
            return res;
        }
    };

  • -1
    Q

    for iterative solution, I use deque in C++, no reverse too.

    for zig, pop back, push front, left then right,

    for zag, pop front, push back, 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
    T

    What is the memory complexity of this code? I'm just wondering whether it is a good idea including a List<List<Integer>> as an argument to the recursive method. Will all recursive steps operate on the same object or will they each create first temporary objects and then merge them. I have also posted my solution below. Can you please tell me where I could improve?


  • 0
    T

    This is my alternate accepted solution. Any suggestions on improvement? I feel like the q.peekLast() step is adding overhead. How to get rid of that in this approach?

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root == null) { return result;}
        
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();
        List<Integer> levelList = new ArrayList<Integer>();
        q.add(root);
        levelList.add(root.val);
        result.add(levelList);
        levelList = new ArrayList<Integer>();
        TreeNode endOfLevel = root;
        int isQueue = -1;
        
        while(!q.isEmpty()) {
            TreeNode node = q.remove();
            if(node.left != null) { 
                q.add(node.left);
                if(isQueue == 1) { levelList.add(node.left.val);}
                else { levelList.add(0, node.left.val);}
            }
            if(node.right != null) { 
                q.add(node.right);
                if(isQueue == 1) { levelList.add(node.right.val);}
                else { levelList.add(0, node.right.val);}
            }
            if(node == endOfLevel) {
                if(!q.isEmpty()) {
                    result.add(levelList);
                    levelList = new ArrayList<Integer>();
                    isQueue = -isQueue;
                    endOfLevel = q.peekLast();
                }
            }
        }
        return result;
    }

  • 0
    W
    This post is deleted!

  • 24
    M

    here is my accepted Java code. Just a little change from the Binary Tree Level Order Traversal

    I use a queue to implement BFS. Each time when I poll a node, I add this node value to level. I use a variable zigzag to indicate whether add from left to right or right to left. If zigzag == false, it is from left to right; if zigzag == true, it is from right to left.
    And from right to left just need to use ArrayList.add(0, value) method

    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    boolean zigzag = false;
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int cnt = queue.size();
        for (int i = 0; i < cnt; i++) {
            TreeNode node = queue.poll();
            if (zigzag) {
                level.add(0, node.val);
            }
            else {
                level.add(node.val);
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        res.add(level);
        zigzag = !zigzag;
    }
    return res;

  • 3
    H

    c++版本:

    void help(vector<vector<int>>& res,  int level, TreeNode* root) {
    	if (res.size() <= level) res.push_back({ root->val });
    	else if(level%2) res[level].insert(res[level].begin(),root->val);
    	else res[level].push_back(root->val);
    	if (root->left) help(res,  level+1, root->left);
    	if (root->right) help(res,  level+1, root->right);
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    	vector<vector<int>> res;
    	if (!root) return res;
    	help(res, 0, root);
    	return res;
    }

  • 0

    I have the same answer, but I'm not sure whether to use recursive solution or iterative one in real interview. Recursive one has really short time, but it seems that a lot of people prefer iterative one. I might be wrong. Could anyone explain it to me?


  • 2

    @marcusgao I like your zigzag variable. Very readable! Here is a shorter version.

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if (root != null) q.offer(root);
        List<List<Integer>> ret = new ArrayList<>();
        for (boolean zigzag = false; !q.isEmpty(); zigzag = !zigzag) {
            List<Integer> level = new LinkedList<>();
            for (int size = q.size(); size > 0; size--) {
                TreeNode n = q.poll();
                level.add((zigzag ? 0 : level.size()), n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            ret.add(level);
        }
        return ret;
    }
    

  • 0

    Nice DFS,

    Here is my BFS:

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList();
            if (root == null) return res;
            Queue<TreeNode> q = new ArrayDeque();
            q.offer(root);
            boolean leftToRight = true;
            int cur = 1, next = 0;
            while (!q.isEmpty()) {
                List<Integer> list = new ArrayList();
                while (cur-- > 0) {
                    TreeNode node = q.poll();
                    if (leftToRight) list.add(node.val);
                    else list.add(0, node.val);
                    
                    if (node.left != null) {
                        q.offer(node.left);
                        next++;
                    }
                    if (node.right != null) {
                        q.offer(node.right);
                        next++;
                    }
                }
                res.add(list);
                cur = next;
                next = 0;
                leftToRight = !leftToRight;
            }
            return res;        
        }
    

  • 0
    B
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            addList(res, root, 0);
            return res;
        }
        
        public void addList(List<List<Integer>> res, TreeNode root, int level){
            if(root == null) return;
            if (level >= res.size()){
                res.add(new LinkedList<Integer>());
            }
            if (level%2 == 1) res.get(level).add(root.val);
            else res.get(level).add(0, root.val);
            addList(res, root.right, level + 1);
            addList(res, root.left, level + 1);
            
        }
    

    Solution I made using my other solution. Not sure what is the difference with yours except the zig zag check, but it beats 90% of java runs. Maybe test case.


  • 0

    In python, the exact solution is not O(n), because inserting at the front of a list is O(n), and the total average complexity is O(nlogn) unless you use deque to cache each level and then convert it to list before finally putting to result.


  • 0
    A

    I think this could be done without queue. Just using arrays and popping the last element. Have a look here:
    https://discuss.leetcode.com/topic/78111/array-based-solution-no-reverse-no-dequeue-using-right-to-left-traverse


Log in to reply
 

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