Simple intuitive iterative solution: O(1) space, Accepted 1ms time


  • 0
    H

    The idea is very simple. We use the TreeLinkNode structure to mimic queue for Level order traversal. We initialize the queue with root. Initially the front and rear point to root. We push front's left and right child to queue. The number of nodes at level h is 2^(h-1). We keep track of current level nodes once it reaches to expected number of nodes, we point it's next to null and reset the current level nodes counter to 0.

    /**

    • Definition for binary tree with next pointer.

    • public class TreeLinkNode {

    • int val;
      
    • TreeLinkNode left, right, next;
      
    • TreeLinkNode(int x) { val = x; }
      
    • }
      */
      public class Solution {
      public void connect(TreeLinkNode root) {
      TreeLinkNode front = root; //The queue front
      TreeLinkNode rear = root; //The queue rear
      int nextLevelNodes = 1; //expected number of nodes in the next level
      int currentLevelNodes = 0; //current number of nodes in next level

      while (front != null) {     //while queue is not empty
      	rear.next = front.left; //add left child of front to the queue 
      	if (rear.next != null)  //check to avoid null pointer exception in the last level
      		rear = rear.next;
      	rear.next = front.right;//add right child of front to the queue 
           
      	if (rear.next != null)
      		rear = rear.next;
      	
           currentLevelNodes++;    //increment the current level counter
           
      	TreeLinkNode next = front.next; //saving the 
      	if (currentLevelNodes == nextLevelNodes) { //once current level counter reaches 2^(h-1) set the front's 
      		front.next = null;                     // next to null;
      		nextLevelNodes *= 2;                   
      		currentLevelNodes = 0;                 //resetting the current level counter
      	}
      	front = next;          // The deque operation
      }
      

      }
      }


Log in to reply
 

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