educative.io

My return value was wrong

Courses
,
#1

Queue queue = new LinkedList<>();
queue.offer(root);

    while(! queue.isEmpty()){
        int levelSize = queue.size();
        for(int i=0; i<queue.size();i++){
            TreeNode temp = queue.poll();

            if(queue.size() == 1){
                temp.next = null;
            }
            else{
                temp.next = queue.peek();
            }
            if(temp.left !=null){
                queue.offer(temp.left);
            }
            if(temp.right !=null){
                queue.offer(temp.right);
            }
            levelSize --;
        }
    }

As my code showing, I use queue.size() to track the element left in the certain level. When queue.size() == 1, it should be the last element of the level and it should point at null, but for the result, I’,m not getting the last element

#2

question for grokking the coding interview, course TBF, section connect level order siblings

#3

Hello @Li_Zengping

I dry ran your code snippet step by step and found two problems in it. Firstly, levelSize-- is not required here in your code snippet. It was just hindering up with the for loop. Secondly, you are polling the element i.e. removing it from queue immediately at the start of the for loop. So for instance root is inside the queue initially. After polling, queue size will NOT be 1. It will be 0. Hence your code flow will point to temp.next = queue.peek() instead of temp.next = null. These two issues combined hindered the overall output of your code. Here’s the updated code snippet:

public static void connect(TreeNode root) {
    if (root == null)
      return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {

      int levelSize = queue.size();

      for (int i = 0; i < levelSize; i++) {

        TreeNode temp = queue.peek();

        if(i == levelSize - 1) {
          temp.next = null;
          queue.poll();
        }

        else {
          queue.poll();
          temp.next = queue.peek();
        }

        if(temp.left !=null) {
           queue.offer(temp.left);
        }

        if(temp.right !=null) {
          queue.offer(temp.right);
        }
      }
    }
  }

Hope this helps!