A concise and easy understanding Java solution


  • 42
    G

    public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) return res;

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean order = true;
        int size = 1;
    
        while(!q.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < size; ++i) {
                TreeNode n = q.poll();
                if(order) {
                    tmp.add(n.val);
                } else {
                    tmp.add(0, n.val);
                }
                if(n.left != null) q.add(n.left);
                if(n.right != null) q.add(n.right);
            }
            res.add(tmp);
            size = q.size();
            order = order ? false : true;
        }
        return res;
    }
    

    }


  • 2
    A

    a few minor nitpicks:

    1. you can initialize variable size inside the while loop : int size = q.size(); and remove one line at the end of while loop. Since int is immutable it won't affect the performance at all, since Java has to allocate 32 bits of memory every loop cycle anyway.

    2. you can replace last line of the while loop with order = !order;

    Now the actual reason I am leaving this comment is that I am surprised that this algorithm performs as well and sometimes even faster than my Deque algo. tmp(0, n.val) should be terribly inefficient, since it copies over the entire arraylist every time a new element is inserted. But this approach still shows the same performance as Deque.... it's a mystery to me.


  • -1
    C

    Pretty concise and neat logic. But variable names are a little bit confusing.


  • 1
    T

    arraylist tmp(0, n.val) should be O(n), but it runs faster than using linkedlist tmp(0, n.val), which should be constant time. strange.

    use arraylist tmp(0, n.val) : 2ms

    use linkedlist tmp(0, n.val): 3ms


  • 0
    F

    Hi, I m wondering what the time complexity is in your solution. Is that O(n²)? I think the size in the last level should be N which is the worst case.


  • 0
    C

    one more concise way for last line
    order = !order


  • 0
    J

    @anton15 This is actually strange, why do you think that is?


  • 0
    H

    Hi, I am a bit confused as to what temp.add(0, n.val) does. How come there are two parameters?


  • 0
    M

    @chigend genius


  • 0
    M

    @GraceLuLi You are a genius!


  • 0
    M

    @hingoman25 It will add the n.val in the first place. Other elements will be moved behind.


Log in to reply
 

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