Can anyone tell me where is my mistake? - Iterative solution in Java using two Linked Lists

  • 0

    I wanted to solve the problem iteratively in Java. To do so, I am using two linked lists - one for the current level and one for the next level. I also keep track of the current level. Below is my program with the coments, if there is anything unclear please tell me.

     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new LinkedList<List<Integer>>();
            if(root == null)    return res;
            List<TreeNode> curr = new LinkedList<TreeNode>();
            int level = 0;
                LinkedList<TreeNode> next = new LinkedList<TreeNode>(); //now next level is empty
                LinkedList<Integer> toAdd = new LinkedList<Integer>();  //linked list of the intereg values
                for(TreeNode node : curr){  //iterate throw the linked list of nodes in the current level
                    if(level%2 == 0){   //if I am at even level, then add first right child, then left child
                        if(node.right != null)  next.add(node.right);
                        if(node.left != null)   next.add(node.left);
                    else{   //if I am at odd level, then add first left child, then right child
                        if(node.left != null)   next.add(node.left);
                        if(node.right != null)  next.add(node.right);
                level++;    //increment level
                res.add(new LinkedList<Integer>(toAdd));    //add current level
                curr = next;    //current level now points to the next level
            return res;

    I received thew Wrong Answer:

    Input: {1,2,3,4,#,#,5}

    Output: [[1],[3,2],[5,4]]

    Expected: [[1],[3,2],[4,5]]

    I don't see where is the problem in my logic?

  • 2

    Apparently, you flipped the order of inserting left and right nodes to the next level, but you should note that you visit all current nodes always in left-to-right order. So, flipping the order of their children will not reverse the order of whole next level.
    For example, in the wrong case you gave, queue level 2 = [3,2], then you add 3's children into the next list first. However, what is expected is that you add 2's children before 3's.
    So my suggestion is: instead of periodically reverse the order of inserting left-right nodes, you reverse the order of inserting current node into the next level. That should fix it.

Log in to reply

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